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!/2$ $9!$

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

Próbka 8 puzzli

artificial-intelligence

— Krzywka
źródło

Ponieważ wykres stanu składa się z dwóch niepowiązanych składników o jednakowej wielkości (całkowita liczba inwersji permutacji każdego stanu jest niezmiennym modułem 2, więc dwa stany, które mają całkowitą liczbę inwersji permutacji nieparzystą, a nawet nie są połączone); Nie mogę znaleźć dobrze wyjaśniony przykład, ale ta prezentacja powinna być jasna na tyle, by zrozumieć go (z wyjątkiem typo „Connected”, które powinny zostać zastąpione „odłączony”)

— Vor

@ Czy zmienić się w odpowiedź?

— Yuval Filmus

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: $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: $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_{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łytki $N$ $N_i$ $T_{\Box}$

N = \sum_{i = 1}^{15} N_{i} + r o w (T_{◻})

$N = \sum_{i=1}^{15} N_i + row(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

— Vor
źródło

Tak jest w przypadku 15 puzzli, ale wydaje się, że wynik można uogólnić również w przypadku 8 puzzli. Dzięki!

— Cam