Search code examples
algorithmartificial-intelligencesliding-tile-puzzle

How many possible states does the 8-puzzle have?

The classical 8-puzzle belongs to the family of sliding blocks. My book (Artificial intelligence A modern approach by Stuart Russell and peter Norwig) says that the 8-puzzle has 9!/2 possible states. But WHY the /2 ? How do you get this?

Solution

  • 9! is the total number of possible configurations of the puzzle, whereas 9!/2 is the total number of solvable configurations. For example, this configuration doesn't have a solution:

    1 2 3
4 5 6
8 7

    Read more about the solvability of certain configurations of the n-puzzle in this Wikipedia article, or as pointed out by @dasblinkenlight in this MathWorld explanation.

    One possible way to find out that 9!/2 is the number of solvable configurations is to start from a solved puzzle and generate all the possible valid, non-repeating movements from it.