How many possible states does the 8-puzzle have?

Question

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 1

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.