Erreichbarer Zustandsraum eines 8-Puzzles

Ich habe gerade angefangen, künstliche Intelligenz zu studieren und frage mich, warum der erreichbare Zustandsraum eines 8-Puzzles . Ich sehe, dass die Anzahl der Permutationen der Kacheln 9 beträgt ! Es ist jedoch nicht sofort ersichtlich, warum die Hälfte der möglichen Zustände des Puzzles in einem bestimmten Zustand nicht erreichbar ist. Kann jemand näher darauf eingehen?$9!/2$$9!$

Ein Bild eines 8-Puzzles als Referenz mit einer zufälligen Konfiguration links und dem Zielzustand rechts:

Dies ist eine Erweiterung dieser Präsentation .

Weil das Zustandsdiagramm aus zwei getrennten Komponenten gleicher Größe besteht. Ohne Beschränkung der Allgemeinheit können wir davon ausgehen , dass der Soll - Zustand ist .$1\;2\;3\;...\;15\;\Box$

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

Bei gegebenem Zustand eine Permutationsinversion eine Kachel T i , die nach T j platziert wird, aber i < j ; Dies geschieht, wenn (a) T i in derselben Reihe von T j liegt , aber rechts davon, oder (b) T i in einer unteren Reihe liegt:$S$$T_i$$T_j$$i < j$$T_i$$T_j$$T_i$

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

Wir definieren als die Anzahl der Kacheln T i , i < j , die nach T j erscheinen . Zum Beispiel im Zustand:$N_j$$T_i$$i < j$$T_j$

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

wir haben, dass nach eine Kachel ( T 6 ) davor sein sollte, also N 7 = 1 ; Nach T 10 gibt es vier Kacheln ( T 7 , T 8 , T 9 , T 6 ), die davor liegen sollten, also N 10 = 4 .$T_{7}$$T_6$$N_7=1$$T_{10}$$T_7, T_8, T_9, T_6$$N_{10}=4$

Sei die Summe aller N i und die Zeilennummer der leeren Kachel T $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$

Beispielsweise:

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

$N \bmod = 0$$N \mod 2 = 1$

Zum Beispiel sind die folgenden zwei Zustände nicht verbunden:

 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