Przeszukiwanie z nawrotami (backtracking)
W szachach za najsilniejszą figurę uważa się królową – potrafi ona atakować pola w tym samym wierszu, w tej samej kolumnie i po skosie. Siła ataku tej figury jest tak duża, że rozstawienie \(8\) nieatakujących się wzajemnie królowych na standardowej szachownicy rozmiaru \(8 \times 8\) jest trudne.
Spróbujmy zaprojektować algorytm znajdujący takie rozstawienie. Zacznijmy od pomysłu najbardziej brutalnego, czyli generowania wszystkich możliwych rozstawień 8 królowych i sprawdzania, czy nie atakują się wzajemnie.
Ponumerujmy pola szachownicy od 0 do 63. Będziemy działać następująco:
- Wstawiamy pierwszą królową na pierwszym wolnym polu.
- Wstawiamy drugą królową na pierwszym wolnym polu o numerze większym niż pole, na którym stoi pierwsza królowa.
- Kontynuujemy dla kolejnych królowych: trzeciej, czwartej itd. W ogólności jeśli \(i\)-ta królowa stoi na polu \(p_i\), to \((i+1)\)-ta królowa stoi na polu \(p_{i+1} > p_i\). Taki sposób przydzielania pól powoduje, że nie powielamy rozstawień królowych oraz nigdy nie rozstawimy dwóch na tym samym polu.
- Gdy już ustawimy w ten sposób 8 figur sprawdzamy, czy to rozstawienie jest poprawne i, jeśli tak, wypisujemy je jako wynik.
- Potem musimy testować inne położenia ósmej królowej przy ustalonych siedmiu pierwszych figurach. Oznaczamy więc pole \(p_8\) jako "zużyte" dla ósmej królowej i wybieramy kolejne wolne pole dla tej figury.
- Gdy skończą się niezużyte pola dla figury ósmej, zdejmujemy ją zupełnie, "cofamy" się do figury siódmej i teraz ją przestawiamy o jedno pole. Potem oczywiście znowu musimy przetestować wszystkie rozmieszczenia figury ósmej, tak jak wcześniej.
- Oczywiście tak samo skończą się kiedyś pola dla siódmej królowej, więc wtedy przesuwamy szóstą i musimy znowu ustawiać siódmą oraz ósmą na wszystkie sposoby. Widać, że uogólniamy sposób działania na wcześniejsze królowe. W ten sposób generujemy wszystkie możliwe rozstawienia ośmiu królowych na szachownicy.
W poniższym programie realizujemy zaproponowany powyżej algorytm z pewnymi uproszczeniami. Najważniejszym z nich jest niejawne rozwiązanie kwestii "zużytych" pól – nigdzie żadnych pól w ten sposób nie oznaczamy ani nie testujemy na okoliczność zajętości, a po prostu implementujemy algorytm w taki sposób, żeby ustawiać figury wyłącznie na "niezużytych" polach.
W tym celu używamy w sposób rekurencyjny funkcji ustaw_figure(). Każdy
poziom rekurencji zajmuje się ustawieniem jednej figury (argument
ktora) na podanym polu (argument gdzie). Następnie wybieramy
w pętli miejsce, na którym będzie stała kolejna królowa i przekazujemy numer
tego pola jako argument do wywołania kolejnego poziomu ustaw_figure().
const int ROZMIAR = 8;
bool szachownica[ROZMIAR * ROZMIAR]; //true jeśli jest królowa, false w p.p.
void ustaw_figure(int gdzie, int ktora)
{
szachownica[gdzie] = true;
if (ktora == ROZMIAR - 1) {
if (sprawdz() == true) {
//znaleźliśmy wynik
}
} else {
//kolejne figury ustawiamy dalej od 'gdzie', w ten sposób
//nie będziemy powtarzać rozstawień
for (int i = gdzie + 1; i < ROZMIAR * ROZMIAR; ++i)
ustaw_figure(i, ktora + 1);
}
szachownica[gdzie] = false;
}
bool sprawdz()
{
//Zrobimy 4 tablice, w których będziemy odznaczali, czy zbity jest:
// - wiersz,
// - kolumna,
// - diagonala,
// - antydiagonala.
//
//Dwie królowe jednocześnie nie mogą być w żadnej z tych linii,
//ponieważ wtedy będą się wzajemnie atakowały.
bool wiersz[ROZMIAR], kolumna[ROZMIAR], diag[2 * ROZMIAR - 1], antydiag[2 * ROZMIAR - 1];
for (int i = 0; i < ROZMIAR; ++i) {
wiersz[i] = false;
kolumna[i] = false;
diag[i] = false;
antydiag[i] = false;
}
for (int i = 0; i < ROZMIAR * ROZMIAR; ++i)
if (szachownica[i] == true) {
int wie = i / ROZMIAR;
int kol = i % ROZMIAR;
int d = wie + kol;
int ad = ROZMIAR - 1 + wie - kol;
//czy któraś linia jest już atakowana?
if (wiersz[wie] || kolumna[kol] || diag[d] || antydiag[ad])
return false;
wiersz[wie] = true;
kolumna[kol] = true;
diag[d] = true;
antydiag[ad] = true;
}
return true;
}
int main()
{
for (int i = 0; i < ROZMIAR * ROZMIAR; ++i)
ustaw_figure(i, 0);
return 0;
}
Warto zauważyć, że powyższy program napisany jest tak, żeby łatwo można było użyć tego samego algorytmu na planszach innego rozmiaru – wystarczy zmienić jedynie stałą w pierwszej linijce kodu.
Technika pokazana powyżej polega na wyczerpującym przeszukiwaniu tzw. przestrzeni stanów. Przez stan rozumiemy w tym przypadku sposób rozmieszczenia 8 królowych na szachownicy. Dokładniej, jest to przeszukiwanie z nawrotami (backtracking), ponieważ jeśli wygenerowany stan nam nie odpowiada, wycofujemy się z częściowej jego wartości i próbujemy generować go odrobinę inaczej. Realizowane jest to łatwo przy użyciu rekurencji, która automatycznie "wraca" do wcześniejszych wywołań.
Dygresja kombinatoryczna
Funkcja ustaw_figure() generuje wszystkie kombinacje bez powtórzeń
ustawienia 8 figur na szachownicy o 64 polach. W ogólności liczbę
takich kombinacji można policzyć korzystając z tzw. symbolu Newtona:
\({n \choose k} = \frac{n!}{k! (n - k)!}\)
gdzie wartości \(n\) i \(k\) oznaczają, że wybieramy \(k\) elementów ze zbioru liczności \(n\). Łatwo policzyć ile jest różnych rozstawień 8 królowych na standardowej szachownicy:
\({64 \choose 8} = \frac{64!}{8! \cdot 56!} = 4,426,165,368\)
Oczywiście łatwo można przystosować kod ww. funkcji do generowania kombinacji bez powtórzeń dla dowolnego \(n\) oraz \(k\) zamiast ustalonego na sztywno \(n = 64\), \(k = 8\).
Przyspieszanie
Jak widać z obliczeń, przestrzeń stanów do przeszukania jest ogromna – wykładnicza względem rozmiarów szachownicy. Jeśli chcemy znaleźć jakiekolwiek rozwiązanie problemu, możemy mieć nadzieję na trafienie dużo wcześniej, niż po ponad 4 miliardach prób. Jeśli jednak potrzebujemy wszystkich możliwych rozstawień 8 królowych, to czeka nas przeszukiwanie zupełne.
Na pierwszy rzut oka można dostrzec, że obecny program generuje wiele rozstawień absolutnie bez sensu układając w łatwo sprawdzalny sposób królowe w tych samych wierszach, kolumnach lub diagonalach. Sprawdzenie poprawności rozstawienia jest wykonywane dopiero na sam koniec, więc jest wykonywane ponad 4 miliardy razy absolutnie niepotrzebnie
Spoiler
Jest dokładnie 92 ustawień 8 niebijących się królowych na szachownicy \(8 \times 8\)).
Zintegrujmy kod funkcji sprawdz() z ustaw_figure() tak, abyśmy
nie zagłębiali się w ustawienia, które z całą pewnością można wcześniej odrzucić
jako niepoprawne:
const int ROZMIAR = 8;
bool wiersz[ROZMIAR], kolumna[ROZMIAR], diag[2 * ROZMIAR - 1], antydiag[2 * ROZMIAR - 1];
bool szachownica[ROZMIAR * ROZMIAR];
void ustaw_figure(int gdzie, int ktora)
{
szachownica[gdzie] = true;
if (ktora == ROZMIAR - 1) {
//znaleźliśmy wynik
} else {
int wie = gdzie / ROZMIAR;
int kol = gdzie % ROZMIAR;
int d = wie + kol;
int ad = ROZMIAR - 1 + wie - kol;
wiersz[wie] = true;
kolumna[kol] = true;
diag[d] = true;
antydiag[ad] = true;
for (int i = gdzie + 1; i < ROZMIAR * ROZMIAR; ++i) {
int wie_nowy = i / ROZMIAR;
int kol_nowy = i % ROZMIAR;
int d_nowy = wie_nowy + kol_nowy;
int ad_nowy = ROZMIAR - 1 + wie_nowy - kol_nowy;
if (!wiersz[wie_nowy] && !kolumna[kol_nowy] && !diag[d_nowy] && !antydiag[ad_nowy])
ustaw_figure(i, ktora + 1);
}
wiersz[wie] = false;
kolumna[kol] = false;
diag[d] = false;
antydiag[ad] = false;
}
szachownica[gdzie] = false;
}
int main()
{
for (int i = 0; i < ROZMIAR; ++i) {
wiersz[i] = false;
kolumna[i] = false;
diag[i] = false;
antydiag[i] = false;
}
for (int i = 0; i < ROZMIAR * ROZMIAR; ++i)
ustaw_figure(i, 0);
return 0;
}
Teraz liczba wywołań rekurencyjnych została znacząco zredukowana (ćwiczenie dla
Czytelnika: sprawdzić jak bardzo). Często taką redukcję nazywa się przycinaniem
drzewa przeszukiwań – gdy przedstawimy wywołania rekurencyjne funkcji
ustaw_figure() jako drzewo, to okaże się, że teraz to drzewo jest
znacząco przerzedzone, zniknęły całe ogromne poddrzewa itd.
Techniki redukujące drzewo przeszukiwań w oparciu o różne triki programistyczne
i obserwacje nazywa się zwykle heurystykami. Kontynuujmy zatem przycinanie
drzewa korzystając z oczywistej obserwacji: w każdym wierszu wstawiamy dokładnie
jedną figurę, więc zamiast iterować po całej szachownicy, iterujmy po wierszach.
Powoduje to jednocześnie, że tablica bool wiersz[ROZMIAR] staje się
niepotrzebna.
const int ROZMIAR = 8;
bool kolumna[ROZMIAR], diag[2 * ROZMIAR - 1], antydiag[2 * ROZMIAR - 1];
int szachownica[ROZMIAR]; //teraz szachownica[i] zawiera numer kolumny,
//w której znajduje się i-ta królowa
void ustaw_figure(int gdzie, int ktora)
{
szachownica[ktora] = gdzie;
if (ktora == ROZMIAR - 1) {
//znaleźliśmy wynik
} else {
//teraz zmienna 'ktora' oznacza numer wiersza, a 'gdzie' numer kolumny
int d = ktora + gdzie;
int ad = ROZMIAR - 1 + ktora - gdzie;
kolumna[gdzie] = true;
diag[d] = true;
antydiag[ad] = true;
for (int i = 0; i < ROZMIAR; ++i) {
//zamiast 'wie_nowy' mamy 'ktora + 1', zamiast 'kol_nowy' mamy 'i'
int d_nowy = ktora + 1 + i;
int ad_nowy = ROZMIAR + ktora - i;
if (!kolumna[kol_nowy] && !diag[d_nowy] && !antydiag[ad_nowy])
ustaw_figure(i, ktora + 1);
}
kolumna[gdzie] = false;
diag[d] = false;
antydiag[ad] = false;
}
}
int main()
{
for (int i = 0; i < ROZMIAR; ++i) {
kolumna[i] = false;
diag[i] = false;
antydiag[i] = false;
}
for (int i = 0; i < ROZMIAR; ++i)
ustaw_figure(i, 0);
return 0;
}
Dalsze heurystyki
W zadaniach związanych z przeszukiwaniem przestrzeni stanów wymyślenie odpowiednio silnych i, przede wszystkim, poprawnych (tzn. nie odrzucających pochopnie stanów pożądanych) jest często kluczem do sukcesu.
Dla problemu niebijących się królowych pozostaje do wykorzystania jeszcze jeden as: gdy znajdziemy jedno rozwiązanie, możemy z niego wygenerować kilka następnych odbijając je symetrycznie oraz obracając. Wiedza o takich rozwiązaniach może być wykorzystana do dalszego przycięcia drzewa przeszukiwań stanów.
Ten pomysł wymaga już nieco większego zaangażowania programistycznego i może być nieopłacalny dla szachownic niewielkiego rozmiaru (w tym szachownicy standardowej \(8 \times 8\)). Zysk wynikający z tej heurystyki może przeważyć koszty obliczeniowe dla szachownic o boku rozmiaru kilkunastu pól.