Zależności między polami na szachownicy
Współrzędne królowych na szachownicy przechowywane są w tablicy liczb całkowitych o nazwie col. Indeksami tej tablicy
są numery wierszy, zaś wartości kolejnych jej elementów to numery kolumn. Np. col[4] = 2 oznacza, że królowa znajduje
się w wierszu 4 i kolumnie 2. Bazując na informacjach zawartych w tablicy współrzędnych, algorytm może skutecznie
określić położenia wszystkich królowych na szachownicy.
... "Szach-mat" ...
Dla przykładu, aby sprawdzić czy dwie królowe znajdują się w tej samej kolumnie, algorytm stosuje porównanie numerów
kolumn, w których znajdują się owe królowe. Jeśli w tablicy col oba wiersze posiadają ten sam numer kolumny, znaczy
to, że królowe usytuowane są w tej samej kolumnie, a więc szachują się nawzajem.
col (wiersz_a) = col (wiersz_b)
Na poniższym rysunku przedstawiono właśnie taką sytuację. Królowa z wiersza pierwszego usytuowana jest w kolumnie numer 1, tak samo jak królowa znajdująca się wiersz niżej.
Aby przekonać się, czy królowa z wiersza nadrzędnego (a) szachuje królową z wiersza podrzędnego (b) po jednej z
przekątnych (rys. 2,3), wystarczy porównać różnicę numerów kolumn i wierszy. Stosuje się w tym celu następującą instrukcję:
abs( col[a] - col[b] ) == b - a
Jeżeli liczby po obu stronach równania są takie same, to mamy do czynienia
z szachowaniem królowych po jednej z przekątnych. Dzięki zastosowaniu wartości bezwzględnej (abs) przy obliczaniu różnicy kolumn, nie było konieczności stosowania dwóch odrębnych instrukcji testujących położenie królowych względem lewej i prawej przekątnej. Na tej podstawie algorytm podejmuje decyzje, czy warto w danym polu umieścić królową, czy może mija się to z celem.
Definicje funkcji
Program rozwiązujący problem n-królowych podzielono na dwie uzupełniające się części: funkcję ustaw_Krolowe i czy_Obiecujacy.
Pierwsza metoda odpowiada za rekurencyjne wypełnianie kolejnych wierszy szachownicy królowymi, zaś druga funkcja spełnia rolę
arbitra decydującego czy dane pole na szachownicy znajduje się w zasięgu innej królowej. Bardziej szczegółową analizę programu,
rozpoczęto od tej drugiej metody. Funkcja czy_Obiecujacy odpowiada za analizę zależności między królową ustawioną
w testowanym wierszu (w_test) a wszystkimi wcześniej ustawionymi królowymi na szachownicy. W pętli while lokalizacje królowych
testowane są parami. Zaczynając od królowej w wierszu pierwszym (w_queen = 1). Algorytm sprawdza, czy królowa z wiersza w_queen
szachuje królową w wierszu w_test. Jeżeli tak, to uznaje pole col[w_test] za niebezpieczne, a zmienna obiecujący przyjmuje wartość
false. Taki wierzchołek, wraz
z wierzchołkami potomnymi nie jest brany pod uwagę w dalszej części obliczeń. Można powiedzieć, że jego rozwinięcie zostało
przycięte (stąd określenie: "przycinanie drzewa przestrzeni stanów"). Jeżeli jednak testowane pole okaże się bezpieczne to
zmienna obiecujący pozostaje bez zmian (domyślnie: true). Następnie algorytm wykonuje kolejny obrót pętli,
w którym sprawdza,
jaki wpływ ma królowa z wiersza drugiego (w_queen = 2) na testowaną królową z wiersza w_test itd.
Na rys. 4 zasymulowano działanie metody czy_Obiecujacy w przypadku szachownicy 4x4. Pierwsze trzy królowe zostały pomyślnie
ustawione i nie kolidują ze sobą. Ostatnia królowa (z wiersza w_test = 4) szachowana jest po prawej przekątnej przez królową
z wiersza trzeciego (w = 3). Fakt ten wychodzi na jaw dopiero przy trzecim obrocie pętli while (dla wiersza 4), w którym
przeanalizowano zależności między dwoma ostatnimi królowymi.
|
Poniżej przedstawiono kompletną implementację funkcji czy_Obiecujący. Metoda przyjmuje tylko jeden parametr, jest nim numer testowanego wiersza. W wierszu tym znajduje się królowa, której lokalizacja rozpatrywana jest w odniesieniu do wcześniejszych królowych.
bool czy_Obiecujacy (int w_test) { int w_queen; bool obiecujacy; w_queen = 1; obiecujacy = true; while (w_queen < w_test && obiecujacy) { if (col[w_test] == col[w_queen] || abs (col[w_test]-col[w_queen]) == w_test - w_queen) obiecujacy = false; w_queen++; } return obiecujacy; }
Drugą, nie mniej ważną częścią programu rozwiązującego problem n-królowych jest metoda ustaw_Krolowe. Funkcja przyjmuje na starcie
tylko jeden parametr w postaci zmiennej w_test, określającym numer aktualnie analizowanego wiersza na szachownicy. Tak naprawdę,
wewnątrz funkcji ustaw_Krolowe testowany wiersz nie jest w żaden sposób modyfikowany, jest on tylko punktem wyjścia do modyfikacji
następnego wiersza (w_test+1). Dlatego pierwsze wywołanie metody ustaw_Krolowe odbywa się
z parametrem w_test = 0 (w ten sposób algorytm rozpocznie pracę od 1 wiersza szachownicy).
Głównym celem funkcji jest ustawienie po jednej królowej w każdym polu następnego w kolejności wiersza szachownicy
(col[w_test+1] = j). Następnie funkcja rekurencyjnie wywołuje samą siebie, tylko że tym razem parametrem funkcji jest numer
aktualnie modyfikowanego wiersza (w_test+1). Po wywołaniu funkcji, od razu sprawdzane są relacje między królowymi metodą
czy_Obiecujący. Jeżeli są "obiecujące" to dana gałąź drzewa przestrzeni stanów jest rozwijana, poprzez kolejne wywołania
funkcji ustaw_Krolowe (dla kolejnych wierszy) itd. Implementacja omawianej metody w języku C wygląda następująco:
void ustaw_Krolowe (int w_test) { int j; int x; if (czy_Obiecujacy (w_test)) if (w_test == n) // Udało się odnaleźć rozwiązanie { // następuje wyświetlenie wyników for (x = 1; x <= n; x++) cout << "wiersz: " << x << ", kolumna: << col[x] << endl; } else for (j=1; j<=n; j++) { col[w_test+1] = j; // Wypełnienie wiersza królowymi ustaw_Krolowe (w_test+1); // Funkcja wywołuje samą siebie // na potrzeby kolejnego wiersza } }
Strategię postępowania funkcji ustaw_Krolowe zobrazowano na rys. 19. Po raz kolejny, za przykład posłużyła szachownica o wymiarach 4x4. Po pierwszym uruchomieniu metody ustaw_Krolowe, wiersz 1 wypełnia się królowymi. Kolejne, rekurencyjne wywołanie tej samej metody owocuje stworzeniem 4 kopii drugiego wiersza, dla każdej królowej z wiersza pierwszego. Następne wywołanie utworzy kolejne kopie dla każdej królowej z drugiego wiersza itd. Na poniższym rysunku widać sposób generowania drzewa przestrzeni stanów za pomocą metody ustaw_Krolowe.
Jak widać, złożoność problemu rośnie bardzo szybko. Na szczęście algorytmy
z powrotami są wręcz stworzone do przetwarzania tak skomplikowanych struktur danych. Dzięki zastosowaniu techniki
przycinania drzewa przestrzeni stanów, algorytm przeanalizuje jedynie ułamek 1 % całego drzewa przestrzeni stanów.
Jednak w przypadku większych szachownic, nawet wspomniany ułamek procenta może okazać się trudnym wyzwaniem obliczeniowym,
tak dla algorytmu z powrotami jak i samego programisty.
PLIKI DO POBRANIA |
|