Proof for Mahjongg Solitaire Solver's basis

First of all we must note that deciding the pairings beforehand makes the game equivalent to a trivial variation in which there are 72 groups of 2 tiles each instead of 36 groups of 4 tiles each. The discussion that follows proves the result for the variation with N groups and 2 tiles per group.

We'll note also that it's a characteristic of this game that removing a pair of tiles does never cause any previously free tile to become blocked. As a side note, that implies that the amount of free tiles plus the amount of removed tiles is a number which never decreases during a game, or in other words, after removing a pair the number of free tiles does not decrease by more than two. This is not important for the proof but I thought it was worth noting.

What we want to prove is: if there is an order in which the tiles can be removed which leads to clearing the board (that's our hypothesis), then any other possible order (possible according to the rules) will also clear the board; that means that if there are several groups free in any given position then no matter which group is removed first, the solution will be reached.

The proof goes as follows: let's number the groups with sequential numbers given by the order in which they have to be removed according to the hypothesis, starting with 1. If both groups i and j (j>i) are free after removing groups 1 through i-1, then removing group j first will obviously not prevent groups i, i+1, i+2, ..., j-1 from being removed (keep in mind that removing a pair won't block any tile), and the position after removing tiles j, i, i+1, ..., j-1 in that order will also obviously be the same as the position after removing them in any other order. This makes the order 1, 2, ..., i-1, j, i, i+1, ..., j-1, j+1, ..., N a new candidate for the hypothesis.

This argument can now be applied repeatedly with the new order, allowing us to generate any possible order and thus completing the proof. Admittedly not very formal but hopefully convincing enough.

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.

Back to the Mahjongg Solitaire article