Mahjong solitaire solving algorithm - not

by Jarno Elonen, 2003-2004

Most Mahjong Solitaire (aka. Taipei, Shanghai, Mahjongg) computer implementations can generate puzzles that are guaranteed to be solvable. Even so, it is impossible to come up with an algorithm that could always solve them. For a proof, consider the following elementary case...

...and the rules of the game:

1. You win the game if you can remove all the tiles from the table.
2. You can only remove a pair of similar tiles, both of which have to have at least one completely free wide (tall) side.

Without further analysis, it is immediately clear that the only way to win the above game is to start by taking out the 1-tiles on top the stack and on the bottom left. There is, however, no way to know which of the left-hand side 1-tiles to pick first without peeking into the tall stack.

(Interestingly, this sort of guess-game is an NP problem but definitely not a P one: if an oracle told you the correct solution, verifying it would be an O(N) operation. I doubt an incomplete information problem like this qualifies as a winner of the CMI Millennium Prize, though. *sigh*..)

If, however, you are allowed to peek under the tiles before taking them (complete-information variant of the game), it is obviously possible to write a solver. See: C program by Pedro Gimeno Fortea and Stam, T.: Solving Mahjong Solitaire Positions (2007).