Reachable state space of an 8-puzzle

Problem Detail: 

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:

Asked By : Cam

Answered By : Vor

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 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16515