Espacio de estado accesible de un 8 rompecabezas

¡Acabo de comenzar a estudiar Inteligencia Artificial y me pregunto por qué el espacio de estado alcanzable de un 8 rompecabezas es $9!/2$ . ¡Veo que el número de permutaciones de las fichas es $9!$pero no es inmediatamente obvio por qué la mitad de los posibles estados del rompecabezas son inalcanzables en cualquier estado dado. ¿Alguien puede dar más detalles?

Una imagen de un rompecabezas de 8 para referencia con una configuración aleatoria a la izquierda y el estado del objetivo a la derecha:

Esta es una expansión de esta presentación .

$1\;2\;3\;...\;15\;\Box$

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

$S$$T_i$$T_j$$i < j$$T_i$$T_j$$T_i$

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

$N_j$$T_i$$i < j$$T_j$

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

$T_{7}$$T_6$$N_7=1$$T_{10}$$T_7, T_8, T_9, T_6$$N_{10}=4$

$N$$N_i$$T_{\Box}$

$N = N_7 + N_8 + N_9 + N_{10} + row(T_{\Box}) = 1 + 1 +1 + 4 + 4=11$

$N$ $N$

Por ejemplo:

 .  .  .  .      .  .  .  .
 .  .  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$

$N \bmod 2$

Podemos concluir que el espacio de estado se divide en dos mitades desconectadas , una con y la otra con .$N \bmod = 0$$N \mod 2 = 1$

Por ejemplo, los siguientes dos estados no están conectados:

 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