Osiągalna przestrzeń stanu 8-puzzli

Właśnie zacząłem studiować sztuczną inteligencję i zastanawiam się, dlaczego osiągalna przestrzeń stanu 8-puzzli to . Widzę, że liczba permutacji płytek wynosiale nie jest od razu oczywiste, dlaczego połowa możliwych stanów układanki jest nieosiągalna w danym stanie. Czy ktoś może opracować?9 $9!/2$$9!$

Obraz 8 puzzli w celach informacyjnych z losową konfiguracją po lewej stronie i stanem bramki po prawej:

To jest rozwinięcie tej prezentacji .

Ponieważ wykres stanu składa się z dwóch odłączonych elementów o równej wielkości. Bez utraty ogólności możemy założyć, że stanem docelowym jest .$1\;2\;3\;...\;15\;\Box$

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

Biorąc pod uwagę stan inwersji permutacji jest dachówka który jest umieszczony po ale ; dzieje się tak, gdy (a) znajduje się w tym samym rzędzie , ale po jego prawej stronie lub (b) znajduje się w dolnym rzędzie:T i T j i < j T i T j T $S$$T_i$$T_j$$i < j$$T_i$$T_j$$T_i$

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

Definiujemy jako liczbę płytek , które pojawiają się po . Na przykład w stanie:T i i < j T $N_j$$T_i$$i < j$$T_j$

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

mamy, że po jest jeden kafelek ( ), który powinien być przed nim, więc ; po są cztery płytki ( ), które powinny być przed nim, więc . T 6 N 7 = 1 T 10 T 7 , T 8 , T 9 , T 6 N 10 = $T_{7}$$T_6$$N_7=1$$T_{10}$$T_7, T_8, T_9, T_6$$N_{10}=4$

Niech będzie sumą wszystkich i numeru wiersza pustej płytkiN i T $N$$N_i$$T_{\Box}$

W powyższym przykładzie mamy:$N = N_7 + N_8 + N_9 + N_{10} + row(T_{\Box}) = 1 + 1 +1 + 4 + 4=11$

Możemy zauważyć, że kiedy pusta płytka jest przesuwana poziomo, się nie zmienia; jeśli przesuniemy pustą płytkę w pionie, zmienia się o parzystą liczbę.$N$ $N$

Na przykład:

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

Zatem jest niezmienny przy każdym legalnym ruchu pustej płytki .$N \bmod 2$

Możemy wnioskować, że przestrzeń stanu jest podzielona na dwie rozłączone połówki, jedna ma a druga ma .$N \bmod = 0$$N \mod 2 = 1$

Na przykład następujące dwa stany nie są połączone:

 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