Reachable state space of an 8-puzzle

 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