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?

Login

0 votes

8-puzzle has a property that exactly half (of all) permutations can be reached from any starting state. 9! is the total number of possible configurations of the puzzle, whereas 9!/2 is the total number of solvable configurations.

Read more about the solvability of certain configurations of the n-puzzle in this Wikipedia __article__

The simple explanation is that **exactly half** the configurations aren't possible to reach from any chosen starting point (or alternatively, can't reach any randomly chosen ending point), so we divide total configurations (9!) by 2 to get the total number of states that can move step by step to the solution.

If you draw a graph of every single state with every single possible transition out of that state you will end up with 9! / 2 states with 9! transitions. There are states that exist but don't fall on the graph and those are the "unsolvable" ones.