33

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?

Ghost
  • 1,777
  • 6
  • 31
  • 44

1 Answers1

34

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.

Óscar López
  • 232,561
  • 37
  • 312
  • 386
  • 1
    While this might be correct, it is not (yet) an explanation for why we have to divide by 2. Or is it? – phimuemue Aug 12 '12 at 16:01
  • So how does the fact that some configurations aren't possible cause us to divide it by 2? – Ghost Aug 12 '12 at 16:02
  • 12
    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 http://www.jimloy.com/puzz/15.htm – Penguino Aug 13 '12 at 00:46
  • 1
    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!. –  Sep 08 '12 at 14:34
  • 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. – mateor Oct 17 '14 at 03:58