headerphoto

Strategia algorytmu z powrotami

Algorytm naiwny

Najprostszym rozwiązaniem problemu n-królowych byłoby wygenerowanie wszystkich możliwych ustawień królowych na szachownicy. Oczywiście bierzemy pod uwagę fakt, że w jednym wierszu powinna znajdować się dokładnie jedna królowa, oraz że królowe nie mogą się nawzajem szachować. Dokonujemy więc przestawień królowych w kolumnach i sprawdzamy czy się nie szachują. Dla przykładu, na szachownicy o wymiarach 5x5 otrzymujemy 5*5*5*5*5 = 3125 potencjalnych rozwiązań, podczas gdy jest ich tak naprawdę tylko 10. Jak widać algorytm naiwny jest bardzo nieefektywny, nawet dla szachownic o dosyć niewielkich rozmiarach.

Algorytm z powrotami

Aby rozwiązać problem n-królowych metodą algorytmów z powrotami, należy najpierw przedstawić szachownicę w postaci drzewa. Każdy z jego poziomów jest odpowiednikiem wiersza na szachownicy. Zaś wierzchołkom przypisane są współrzędne konkretnych pól. Konwersja małej szachownicy o wymiarach 2x2 do postaci drzewa przestrzeni stanów Zilutrowałem na rysunku 1.


Rys 1. Konwersja szachownicy do postaci drzewa


Warto tutaj zaznaczyć, że każdy wierzchołek nie będący liściem ma zawsze taką samą ilość węzłów potomnych. Ilość ta jest uzależniona od liczby kolumn (lub wierszy) w danej szachownicy.

Celem algorytmu jest odnalezienie wszystkich możliwych kombinacji ustawień królowych na szachownicy o zadanym rozmiarze. Dzięki zastosowaniu techniki przeszukiwania w głąb, algorytm z powrotami nie musi generować od razu wszystkich możliwych rozwiązań (jak algorytm naiwny). Może dojść do nich poprzez analizę każdego napotkanego węzła i cofać się w drzewie przestrzeni stanów, jeśli uzna dany węzeł za nieobiecujący.

Schemat postępowania algorytmu z powrotami dla problemu n-królowych

- Algorytm rozpoczyna ustawianie figur od lewego górnego rogu szachownicy. Po umieszczeniu królowej w polu [1,1], przechodzi o poziom niżej i sprawdza, w którym polu może ustawić następną królową.
- Pola [2,1] oraz [2,2] uznaje są za niebezpieczne (w odniesieniu do drzewa byłyby to węzły nieobiecujące). Pola te są atakowane przez królową z wiersza 1, dlatego algorytm pomija je, a królową ustawia w pierwszym bezpiecznym polu, czyli [2,3] (węźle obiecującym)
- Analizując wiersz 3 okazuje się, że nie jesteśmy w stanie umieścić w nim żadnej królowej. W tym momencie po raz pierwszy algorytm używa techniki powrotów, aby wrócić się do królowej z poprzedniego poziomu (czyli pola [2,3])
- Algorytm cofa się i przestawia królową z wiersza 2 w inne, bezpieczne miejsce (a więc następuje przesunięcie królowej z pola [2,3] do [2,4]).
- Teraz trzecią królową możemy ustawić w polu [3,2] (pozycja ta nie znajduje się w polu rażenia żadnej innej królowej)
- Przy takim ustawieniu królowych (w trzech pierwszych wierszach), nie znajdziemy bezpiecznego pola w wierszu 4. Algorytm cofa się więc znowu o poziom w górę i próbuje znaleźć następne bezpieczne pole dla królowej z wiersza 3, w nadziei że jej przestawienie zaowocuje możliwością bezpiecznego ustawienia królowej w wierszu 4.
- Okazuje się jednak, że w wierszu 3 nie ma już żadnego bezpiecznego pola. Cofnięcie się o kolejny poziom i przestawienie królowej w wierszu 2 również nie jest możliwe (królowa z wiersza 2 jest już na prawym skraju szachownicy).
- Zatem algorytm cofa się o dwa poziomy, kasując przy tym królową w wierszu 2 i przestawia w następne, bezpieczne miejsce królową z wiersza 1. Jest to pole [1,2]. Uznaje tym samym, że wszystkie kombinacje ścieżek zaczynających się od królowej w polu [1,1] nie są w stanie doprowadzić nas do rozwiązania.
- W wierszu 2 jedynym bezpiecznym polem do ustawienia królowej jest teraz pole [2,4].
- Bezpieczne pole dla królowej z wiersza 3 to pole [3,1].
- W ostatnim, 4 wierszu, znajdujemy bezpieczne miejsce dla królowej w polu [4,3].

Powyższe rozwiązanie ilustruje metodę postępowania algorytmu z powrotami, w odniesieniu do prawdziwej szachownicy. Jednak jak wiadomo, algorytm nie analizuje szachownicy w jej rzeczywistej postaci, analizuje pewną abstrakcyjną strukturę danych, zwaną drzewem przestrzeni stanów. Każde przetestowane pole na szachownicy to odwiedzony wierzchołek. Węzły obiecujące przesuwają algorytm w głąb drzewa, umożliwiając mu (teoretycznie) zbliżenie się do rozwiązania. Wynikiem tego jest przycięte drzewo przestrzeni stanów, składające się z odwiedzonych wierzchołków. Na rysunku 2 znajduje się takie właśnie drzewo dla przykładowej szachownicy 4x4. Węzły zaznaczone krzyżykiem to węzły określone przez algorytm jako nieobiecujące. Rozwiązanie zostało znalezione w węźle [4,3], do którego prowadzi ścieżka przez węzły [1,2], [2,4], [3,1].

Rys 2. Przycięte drzewo przestrzeni stanów dla szachownicy 4x4
(po odnalezieniu pierwszego rozwiązania).


Algorytm z powrotami nie zatrzymuje się po odnalezieniu pierwszego rozwiązania, tylko kontynuuje testowanie pól aż do wyznaczenia wszystkich możliwych kombinacji ustawień królowych na danej szachownicy. Dla szachownicy 4x4 mamy tylko dwie takie kombinacje, ale już przy szachownicy 8x8 otrzymujemy ich aż 92.