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?

Signalment

There is an explanation on MathWorld. – Nickelson

Answer 1

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.

Chromogenic

While this might be correct, it is not (yet) an explanation for why we have to divide by 2. Or is it? – Outside

So how does the fact that some configurations aren't possible cause us to divide it by 2? – Signalment

The simple explanation is that exactly half the configurations aren't possible to reach from any chosen starting point (or alternately, 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 want to know why exactly half cannot be reached you will need to learn about "parity". A reasonable starting point is jimloy.com/puzz/15.htm – Suited

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. It just happens that it's half of 9!. – Nonconductor

I would quibble with the first sentence. We may be able to place 8 blocks on 9 spaces in 9! configurations, but there are only 9!/2 reachable configurations of this sliding puzzle. – Clog