Mahjongg Solitaire


Contents of this section

My solving algorithm used to be posted here. It has been obsoleted by Michiel de Bondt's algorithm which is much superior in terms of speed.

Here's what you can find here now, apart from the description of the game below:

About Mahjongg Solitaire - Introduction to the game and the solver algorithm

Mahjongg Solitaire is a tile matching game written by Brodie Lockard in 1981, and it has become extremely popular since. Activision published it in 1986 under the name Shanghai® using tiles from a chinese four-player game called Mahjong. For this reason it is often also called Mahjongg Solitaire and sometimes just Mahjongg, which is indeed annoying for the players of the real Mahjong game for the confusion it causes. Other names I've seen around are: Taipei, Solitile, The Turtle, and variants of the name Mahjongg such as Mah Jong, Mahjong, Majong, Mah-Jongg, either with or without the “Solitaire” suffix or prefix. Since Shanghai® is a registered trademark by Activision and the game is even more widely known as Mahjongg Solitaire I'll be using this name. See also http://home.halden.net/vkp/vkp/history.html for more information about the history of the game. That site also holds lots of information which will be of interest to people who want to know more about it.

The idea of the game is as follows: the tiles are organized in a layout, usually with some of the tiles covering others (there can be several layers of tiles). The usual tile position units (X and Y coordinates) are half a tile's width or height; for the piled tiles (Z coordinate) the usual units are one whole tile's thickness. A tile is considered to be blocked either if there is a tile covering it (even partially, but touching it), or if there is at least one tile touching its left side AND at least one tile touching its right side. A tile that is not blocked is said to be free. A move consists of removing two matching free tiles. Two tiles are said to match if they belong to the same group; in the most usual variants there are four tiles per group (always an even number, in any case) and 36 groups, i.e. 144 tiles in total. The object of the game can vary depending on the variant played, as we'll se later, but in the case we're interested in, the aim is to remove all tiles by making moves.

A board (a layout holding a shuffled arrangement of tiles in a certain order) is said to be solved if all the tiles are removed. We'll use the term “position” to refer to the combination of tiles present or absent in the board after any given number of moves.

It's not always possible to remove all tiles; the layout has a strong influence on the probability that a random shuffle of tiles results in a solvable board. Let's examine three extreme cases. One of them is a layout in which each tile is piled on top of the previous one (144 layers in total with the 36-group, 4-tiles-per-group convention); obviously there's just one single tile free at start and there's no possible first move no matter the arrangement. Another pathological case is all of the tiles placed in a single vertical column. In this case all tiles are free and the game is trivial. The last one is a horizontal row of tiles; for this layout, most random arrangements will make the game unsolvable, and only the arrangements that are symmetric (which are extremely unlikely for uniformly distributed permutations) will be solvable but will also make the game trivial.

With some layouts, though, it's not so easy to determine whether a given board is solvable or not. There is a proof showing that this problem belongs to the NP-complete class in the general case, so now we know which kind of problem we're dealing with.

There are various ways to play the game: as a puzzle, against the clock, against another player, etc. either with or without a scoring system. The goal in some variants is to maximize the score, which often accounts for the time taken by removing tiles and it may happen that the player can obtain a higher score by playing quickly, even if the board is not cleared, than by clearing it. We're only interested in the puzzle variant: the player must find a way of removing all tiles until the board is solved. There is no limit to the number of retries, and the acquired experience usually plays a fundamental role for the success. Using undo or hint features is sometimes considered cheating; if you make a wrong move, you have to start again.

The variant just described belongs to the class of games called “perfect-information games”. There's a proof that there's no deterministic algorithm to solve the solitaire but the proof applies only to the not perfect-information variant and not to this one, i.e. it assumes that the information presented to the solving algorithm is only the tile faces that are visible to a player during a single game. For that version, the choice of the best strategy is a problem whose complexity in the general case has been proved to be PSPACE-hard (the paper is in PDF format). In a nutshell, PSPACE-hard means that it's believed to be much harder than a NP-complete problem. Here we assume full knowledge of the board's contents even for tiles totally covered, so these objections don't apply.

Some of the Mahjongg Solitaire playing programs have the option to generate boards that are guaranteed to be solvable. However, my own experience says these boards tend to be easier to solve on average than boards coming from a random permutation of tiles, and I consider them to be less interesting. There are other programs which generate biased shuffles.

Here's the sketch of an algorithm to generate boards that are always solvable: starting with a board full of unmarked tiles, take pairs of free tiles at random, taking note of which pairs you take. You will eventually either clear the board, or run into a blockade (imagine for example that you end up with the last two tiles being one on top of the other), but with most layouts that's rare, and retrying from the beginning should suffice to clear the board. Now go back to the full board and mark the pairs of tiles that you removed with matching groups chosen at random, keeping track of the number of tiles remaining of each group.

But, as previously stated, that algorithm tends to generate biased shuffles that, in my experience, are frequently easier to solve than random shuffles.

Visit the Mahjongg Solitaire Solver algorithm page for an explanation of a method for solving boards.

Back

Use this address to send me E-mail: parigalo@formauri.es.
NOTE: THIS ADDRESS IS NOT PERMANENT. Always verify this page to send me E-mail because it's likely to change often for spam reasons.

Any kind of suggestions are welcome.


© Copyright 1998,1999,2000,2002,2003,2004,2005,2007 Pedro Gimeno Fortea. All rights reserved.
This is valid HTML 4.01.