2
$\begingroup$

I was playing Mahjongg solitaire the other day.

enter image description here

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.

$\endgroup$
  • $\begingroup$ I think you need to address the issue of how to lay out the tiles for arbitrary $n$ before it even makes sense to start thinking about an answer. $\endgroup$ – Peter Taylor Jan 24 '16 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.