Espace d'état accessible d'un puzzle de 8

Je viens de commencer à étudier l'intelligence artificielle et je me demande pourquoi l'espace d'état accessible d'un puzzle de 8 est . Je vois que le nombre de permutations des tuiles est demais il n'est pas immédiatement évident pourquoi la moitié des états possibles du puzzle sont inaccessibles à un état donné. Quelqu'un peut-il élaborer?$9!/2$$9!$

Une image d'un 8-puzzle pour référence avec une configuration aléatoire à gauche et l'état de l'objectif à droite:

Il s'agit d'une extension de cette présentation .

Parce que le graphique d'état se compose de deux composants déconnectés de taille égale. Sans perte de généralité, nous pouvons supposer que l' état cible est .$1\;2\;3\;...\;15\;\Box$

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

Étant donné un état une inversion de permutation est une tuile qui est placée après mais ; cela se produit lorsque (a) est dans la même rangée de , mais à sa droite, ou (b) est dans une rangée inférieure:$S$$T_i$$T_j$$i < j$$T_i$$T_j$$T_i$

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

Nous définissons comme le nombre de tuiles , qui apparaît après . Par exemple, dans l'état:$N_j$$T_i$$i < j$$T_j$

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

nous avons qu'après il y a une tuile ( ) qui devrait être devant, donc ; après il y a quatre tuiles ( ) qui devraient être devant, donc .$T_{7}$$T_6$$N_7=1$$T_{10}$$T_7, T_8, T_9, T_6$$N_{10}=4$

Soit la somme de tous les et le numéro de ligne de la tuile vide$N$$N_i$$T_{\Box}$

Dans l'exemple ci-dessus, nous avons:$N = N_7 + N_8 + N_9 + N_{10} + row(T_{\Box}) = 1 + 1 +1 + 4 + 4=11$

On peut remarquer que lorsque la tuile vide est déplacée horizontalement, ne change pas; si nous déplaçons la tuile vide verticalement, change d'une quantité paire.$N$ $N$

Par exemple:

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

Donc est invariant sous n'importe quel mouvement légal de la tuile vide .$N \bmod 2$

Nous pouvons conclure que l'espace d'état est divisé en deux moitiés déconnectées , l'une ayant et l'autre ayant .$N \bmod = 0$$N \mod 2 = 1$

Par exemple, les deux états suivants ne sont pas connectés:

 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