11
$\begingroup$

I've just began studying Artificial Intelligence and am wondering why the reachable state space of an 8-puzzle is $9!/2$. I see that the number of permutations of the tiles is $9!$ but it is not immediately obvious why half the possible states of the puzzle are unreachable at any given state. Can anyone elaborate?

An image of an 8-puzzle for reference with a random configuration on the left and the goal state on the right:

Sample 8-puzzle

$\endgroup$
  • 3
    $\begingroup$ Because the state graph consists of two disconnected components of equal size (the total number of permutation inversions of every state is invariant modulo 2, so two states that have a total number of permutation inversions odd and even are not connected); I didn't find a well explained example, but this presentation should be clear enough to let you understand it (except the typo "connected" that should be replaced with "disconnected") $\endgroup$ – Vor Oct 28 '13 at 22:22
  • $\begingroup$ @Vor turn into an answer? $\endgroup$ – Yuval Filmus Oct 29 '13 at 7:54
12
$\begingroup$

This is an expansion of this presentation.

Because the state graph consists of two disconnected components of equal size. Without loss of generality we can assume that the target state is $1\;2\;3\;...\;15\;\Box$.

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  *

Given a state $S$ a permutation inversion is a tile $T_i$ that is placed after $T_j$ but $i < j$; this happens when (a) $T_i$ is in the same row of $T_j$, but on its right, or (b) $T_i$ is in a lower row:

 .  .  .  .      .  .  .  .
 3  .  .  1      .  7  .  .
 .  .  .  .      .  5  .  .
 .  .  .  .      .  .  .  .
    (a)             (b)

We define $N_j$ as the number of tiles $T_i$, $i < j$ that appears after $T_j$. For example, in the state:

 1  2  3  4
 5 10  7  8
 9  6 11 12
13 14 15  *

we have that after $T_{7}$ there is one tile ($T_6$) that should be before it, so $N_7=1$; after $T_{10}$ there are four tiles ($T_7, T_8, T_9, T_6$) that should be before it, so $N_{10}=4$.

Let $N$ be the sum of all $N_i$ and the row number of the empty tile $T_{\Box}$

$$N = \sum_{i=1}^{15} N_i + row(T_{\Box})$$

In the example above we have: $N = N_7 + N_8 + N_9 + N_{10} + row(T_{\Box}) = 1 + 1 +1 + 4 + 4=11$

We can notice that when the empty tile is moved horizontally $N$ doesn't change; if we move the empty tile vertically $N$ changes by an even quantity.

For example:

 .  .  .  .      .  .  .  .
 .  .  2  3      .  .  *  3
 4  5  *  .      4  5  2  .
 .  .  .  .      .  .  .  .

$N' = N + 3 \mbox{ (2 is placed after 3,4,5)} - 1 \mbox{ (empty tile is moved up)} = N + 2$

 .  .  .  .      .  .  .  .
 .  .  *  4      .  .  3  4
 2  5  3  .      2  5  *  .
 .  .  .  .      .  .  .  .

$N' = N + 1 \mbox{ (2 is placed after 3)} - 2 \mbox{ (4,5 are placed after 3)} + 1 \mbox{ (empty tile is moved down)} = N$

So $N \bmod 2$ is invariant under any legal move of the empty tile.

We can conclude that the state space is split in two disconnected halves, one having $N \bmod = 0$ and the other having $N \mod 2 = 1$.

For example the following two states are not connected:

 1  2  3  4     1  2  3  4
 5  6  7  8     5  6  7  8
 9 10 11 12     9 10 11 12
13 14 15  *    13 15 14  *  
    N = 4         N = 5
$\endgroup$
  • $\begingroup$ This is the case for a 15-puzzle but it seems that the result can be generalized for an 8-puzzle as well. Thanks! $\endgroup$ – Cam Nov 11 '13 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.