I was playing Mahjongg solitaire the other day.
It got me thinking...
The board has $2n$ pieces at the beginning and assuming that the game is winnable. The game would be trivial if there would be just one or $n$ types of tiles. The question is what is the optimal number of tile types so that the game is the most difficult?
But what is the most difficult?
Terminology:
open tile: The tile can be moved either left or right without disturbing other tiles.
valid move: Removing of two matching open tiles.
state: An arrangement of tiles on the board.
winnable state: There exists a sequence of valid moves that removes all the tiles.
blocked state: No valid move can be preformed.
reachable state: The state A is reachable from the state B iff there exists a sequence of valid moves that transform B to A. If B is not specified then it is assumed to be the starting state.
Here is one simple way how to measure the difficulty:
difficulty of a state: Is the number of blocked states reachable from current state.
Here goes the question:
For the fixed shape of the game with $2n$ tiles, what is the number of tile types for which the average game has the highest difficulty? Given that there are roughly the same number of tiles of each type and each starting state is winnable.