How many possible states does the 8-puzzle have?

algorithm artificial-intelligence sliding-tile-puzzle
Ghost picture Ghost · Aug 12, 2012 · Viewed 22.9k times · Source

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?

Answer

Óscar López picture Óscar López · Aug 12, 2012

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.

Related questions

8 puzzle: Solvability and shortest solution

I have built a 8 puzzle solver using Breadth First Search. I would now want to modify the code to use heuristics. I would be grateful if someone could answer the following two questions: Solvability How do we decide whether an 8 …

Read More
What is the optimal algorithm for the game 2048?

I have recently stumbled upon the game 2048. You merge similar tiles by moving them in any of the four directions to make "bigger" tiles. After each move, a new tile appears at random empty position with a value of either 2 …

Read More
What are good examples of genetic algorithms/genetic programming solutions?

Genetic algorithms (GA) and genetic programming (GP) are interesting areas of research. I'd like to know about specific problems you have solved using GA/GP and what libraries/frameworks you used if you didn't roll your own. Questions: What problems …

Read More