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.

Answer 2

The feature of the 8-puzzle is that from any initial condition, exactly half (of all) permutations can be attained. The puzzle's total number of conceivable configurations is 9!, whereas the total number of configurations that can be solved is 9!/2.

See this Wikipedia article for additional information on the solvability of specific n-puzzle configurations.https://en.wikipedia.org/wiki/15_puzzle#Solvability

To put it simply, we divide the total number of configurations (9!) by 2 to determine the total number of states that can proceed step-by-step to the solution because exactly half of the configurations cannot be reached from any randomly selected starting point (or, conversely, cannot reach any randomly selected ending point).

If you create a graph that shows every state along with every conceivable transition from that state, you will eventually