headerphoto

Implementacja algorytmu w języku C++ (PLIKI DO POBRANIA NA KOŃCU STRONY)

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.


Rys. 1. Testowanie położenia królowych względem kolumn - szachowanie po kolumnie.


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


Rys. 2. Testowanie położenia królowych względem prawej przekątnej.



Rys. 3. Testowanie położenia królowych względem lewej przekątnej.


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.

Obrót pętli
w_queen
w_test
Obiecujący
Działanie
1
1
4
true
kontynuuj
2
2
4
true
kontynuuj
3
3
4
false
zakończ

Rys. 4. Symulacja działania metody czy_Obiecujący, dla szachownicy 4x4.


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.



Rys. 5. Rekurencyjne tworzenie drzewa przestrzeni stanów poprzez metodę 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
Nazwa
OS
Rozmiar Pobierz plik
Screenshot
Problem n-królowych (exe + src) Windows 400 kb.
Problem n-królowych (exe + src)
Najpierw zainstaluj klasę MCC_ImgButton
AmigaOS 143 kb.
Problem n-królowych (src)
Unix
1.6 kb.