Problem N hetmanów

Jest to problem szachowy i matematyczny, sformułowany w połowie XIX w. przez Maksa Bezzela i Franza Naucka. Dotyczy on takiego rozmieszczenia N hetmanów na szachownicy o wymiarach N×N, aby żadne dwie figury nie szachowały się wzajemnie, czyli aby nie znajdowały się w tym samym wierszu, kolumnie, czy ukośnym rzędzie. Początkowo rozważano zwykłą szachownicę (N = 8), ale z czasem rozszerzono problem na dowolną (kwadratową) szachownicę. Oto przykładowe ustawienie hetmanów na kilku szachownicach (źródło obrazka: Level X Games):

nqueen.jpg

Rozważmy na razie zwykłą szachownicę i spróbujmy oszacować, ile operacji musimy wykonać w celu znalezienia wszystkich rozwiązań problemu. Jeśli chcemy rozważyć wszystkie możliwe przypadki rozmieszczenia 8 hetmanów na 64-polowej szachownicy, otrzymujemy gigantyczną liczbę $\left({64\atop 8}\right)$= 4426165368 operacji. Możemy nieco ograniczyć tę liczbę, jeśli rozważać będziemy tylko takie ustawienia, gdzie w jednym wierszu znajduje się tylko jeden hetman. Nadal jest to bardzo duża liczba równa 88 = 16777216. Wynik możemy jeszcze zmniejszyć żądając, aby w każdym wierszu i w każdej kolumnie znajdował się dokładnie jeden hetman. Ilość możliwości jest w tym przypadku równa ilości permutacji ośmioelementowego zbioru, czyli 8! = 40320. Dla takiej szachownicy nie jest to jeszcze tak wiele, ale silnia rośnie bardzo szybko i dla większych szachownic złożoność obliczeniowa będzie nie do przyjęcia. Spróbujemy zatem rozwiązać ten problem przy pomocy algorytmu z powrotami.

Podstawą naszego algorytmu będzie funkcja test(c), której zadaniem będzie wypróbowanie wszystkich możliwych ustawień hetmana w kolumnie o numerze c. Dla każdego takiego ustawienia wywoływana będzie funkcja test(c+1), próbująca ustawić hetmana w następnej kolumnie. Jeśli wyczerpią się wszystkie możliwości w kolumnie c, wtedy funkcja test(c) kończy działanie i wracamy do funkcji test z poprzedniej kolumny. Jeśli uda się ustawić hetmana w ostatniej kolumnie, wtedy wypisywana jest konfiguracja hetmanów, czyli kolejne rozwiązanie problemu i wracamy do przedostatniej kolumny. Jeśli funkcja test z pierwszej kolumny zakończy działanie, będzie to również koniec całego algorytmu.

Kluczem do efektywności algorytmu jest szybkie sprawdzanie, czy na danym polu można ustawić hetmana. Możemy uczynić to w czasie stałym, jeśli będziemy pamiętać, które wiersze i ukośne rzędy są szachowane przez dotychczas ustawione hetmany. Numerów szachowanych kolumn nie musimy pamiętać, gdyż nasz algorytm ustawia za każdym razem jednego hetmana w kolejnej kolumnie. Potrzebujemy w tym celu trzech tablic logicznych: row o wymiarze N (dla wierszy) i dwóch up oraz down o wymiarach 2N-1 (dla ukośnych rzędów). Elementom tych tablic przypisujemy na początku wartość false.

Na przykład dla N = 4 mamy numerację wierszy i kolumn:

queens02.gif

oraz przyjmujemy numerację rzędów ukośnych w jedną i drugą stronę:

queens03.gif

Pole szachownicy w wierszu r i kolumnie c należy do rzędu up[r+c-1] oraz do rzędu down[r-c+N].

Funkcja possible sprawdzająca, czy na polu (r,c) można postawić hetmana, ma postać:

possible(r,c)
   return !row[r] && !up[r+c-1] && !down[r-c+N]

Numery wierszy, w których stoją hetmany w poszczególnych kolumnach przechowamy w tablicy solution o rozmiarze N. Funkcja put ustawia hetmana na polu (r,c):

put(r,c)
   solution[c] = r
   row[r] = up[r+c-1] = down[r-c+N] = true

Z kolei funkcja remove usuwa hetmana:

remove(r,c)
   row[r] = up[r+c-1] = down[r-c+N] = false

Czas teraz na główną funkcję test:

test(c)
   for r=1 to N do
      if possible(r,c)
         put(r,c)
         if c==N
            print solution
         else
            test(c+1)
         remove(r,c)

Wykonanie całego algorytmu i znalezienie wszystkich rozwiązań następuje po wywołaniu test(1). Na przykład dla N = 4 otrzymujemy dwa rozwiązania:

queens04.gif

Jak widać, nie są to rozwiązania niezależne, gdyż jedno można otrzymać z drugiego przez odbicie.

Dla N = 8 otrzymujemy 92 rozwiązania, z czego tylko 12 jest niezależnych, a pozostałe powiązane są z nimi przez odbicia i obroty. W tym przypadku funkcja test wywoływana jest 1965 razy, co daje znacznie lepszy wynik niż 8! = 40320. Dla coraz większych N różnica ta jeszcze bardziej pogłębia się (wykładniczo, na korzyść algorytmu z powrotami). Dzieje się tak dlatego, że algorytm z powrotami przerywa rekurencyjne zagłębianie się już w momencie, gdy nie da się postawić kolejnego hetmana, a nie ustawia wszystkie hetmany i dopiero wtedy ocenia poprawność konfiguracji.

Powrót do Algorytmy wykładnicze

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License