Przedstawienie problemu

Hetman, potocznie zwany królową, jest uznawany za najsilniejszą figurę w szachach. Wynika to z faktu, że może on poruszać się o dowolną liczbę pól poziomo, pionowo i na ukos.

Spróbujmy ustawić na szachownicy osiem figur hetmanów w taki sposób, aby żaden z nich nie atakował któregokolwiek z siedmiu pozostałych. Na tym właśnie polega problem ośmiu hetmanów.

Skąd wzięła się cyfra osiem? Na standardowej szachownicy nie możemy umieścić więcej niż osiem figur hetmanów przy założeniu, że nie wolno im się atakować. Hetman zagraża wszystkim polom znajdującym się w liniach poziomych i pionowych. Szachownica ma wymiary 8 na 8 pól. Hetman, który nie atakuje innych hetmanów, musi być jedyną figurą zarówno w wierszu, jak i w kolumnie. Na szachownicy umieścimy zatem najwyżej ośmiu hetmanów.

Na czym polega problem ośmiu hetmanów?

W rozwiązaniu tego problemu chodzi o takie rozstawienie ośmiu hetmanów na tradycyjnej szachownicy wielkości 8 x 8 pól, aby figury te wzajemnie się nie atakowały. Naszym celem jest znalezienie wszystkich możliwych takich rozmieszczeń.

Na początek przypomnijmy sobie, w jakich kierunkach porusza się hetman (zwany też królową). Na poniższym rysunku przedstawione są wszystkie dostępne ruchy hetmana. Widzimy, że może się on przesuwać się poziomo, pionowo i na ukos, a w dodatku o dowolną liczbę pól.

RTSlzGxWHiIkP

Ilustracja przedstawia białą figurę hetmana na czarnym polu na środku szachownicy d5.
Iksami zaznaczono pola, po których figura ta może się poruszać.
Zaznaczony jest rząd pól pionowych, poziomych, oraz po skosach od pola, na którym stoi hetman. Poziom pól szachownicy oznaczony jest literami od a do h a pion od 1 do 8.

Jeżeli chcemy ustawić dwie królowe na jednej planszy tak, aby sobie wzajemnie nie zagrażały, drugą królową ustawić musimy w takim miejscu, aby nie znajdowała się w zasięgu ruchu tej pierwszej. A zatem nie możemy postawić jej na polu ze znakiem X:

R1IdbXDd0p0yc

Ilustracja przedstawia białą figurę hetmana na czarnym polu na środku szachownicy na polu d5.
Iksami zaznaczono pola, po których figura ta może się poruszać.
Zaznaczony jest rząd pól pionowych, poziomych, oraz po skosach od pola, na którym stoi hetman. Poziom pól szachownicy oznaczony jest literami od a do h a pion od 1 do 8. Drugi hetman ustawiony jest na polu bez iksa C8.

Przy dwóch hetmanach zadanie wydaje się bardzo proste. Co jednak w sytuacji, gdy musimy ustawić ich aż osiem?

Wiemy, że dwa hetmany nie mogą pojawić się w jednej kolumnie, w jednym wierszu ani w jednej ukośnej linii. Zatem jeżeli przyjmiemy, że współrzędne pierwszego hetmana to (a, b), a drugiego - (c, d), to figury te:

• nie mogą znajdować się w tej samej kolumnie:

• nie mogą znajdować się w tym samym wierszu:

• nie mogą znajdować się na tej samej przekątnej, co jest równoważne z tym, że różnica wierszy między nimi nie może być równa różnicy kolumn:

Rozwiązanie problemu

Rozwiązanie problemu będzie przedstawione w postaci ciągu ośmiu liczb, gdzie indeks danego elementu oznacza numer kolumny, a jego wartość to numer wiersza, w którym znajduje się hetman. Na przykład 61528374 oznacza tyle, że w kolumnie pierwszej hetman znajduje się w szóstym wierszu, w kolumnie drugiej - w wierszu pierwszym itd.

Dla rozwiązania 61528374 szachownica wygląda tak:

R15ykqr8SQxfT

Ilustracja przedstawia szachownicę z hetmanami ustawionymi na polach: a6, b1, c5, d2, e8, f3, g7 oraz h4. Poziom pól szachownicy oznaczony jest literami od a do h a pion od 1 do 8.

Na początku ustawiamy wszystkie elementy na zero, a zatem nasz początkowy ciąg będzie następujący: 00000000.

Zaczynamy od pierwszego wiersza. Szukamy w nim kolumny, która nie jest zajęta przez innego hetmana, to znaczy ma wartość 0. Pierwszą znalezioną kolumną jest kolumna nr 1. Zatem w tablicy o indeksie 1 zapisujemy wartość wiersza, czyli 1.

RFYw9EcxxkJU1

Ilustracja przedstawia hetmana ustawionego na polu a1.
Iksami zaznaczono pola, na które figura ta może się poruszyć.
Całą kolumnę a, cały rząd 1, oraz po ukosie od a1 do h8. Poziom pól szachownicy oznaczony jest literami od a do h, a pion od 1 do 8.

Następnie zajmujemy się wierszem drugim. Szukamy kolumny, która nie jest zajęta przez innego hetmana i w której żadne pole nie jest atakowane. Powyższe warunki dla drugiego wiersza spełnia kolumna nr 3, 4, 5, 6, 7, 8. Wybieramy pierwszą z możliwości, a więc na trzecim miejscu w naszym kodzie umieszczamy dwójkę. Po tych dwóch krokach ciąg liczb wygląda tak: 10200000.

RMO6mDClJojsU

Ilustracja przedstawia hetmana ustawionego na polu a1.
Iksami zaznaczono pola, na które figura ta może się poruszyć.
Cały rząd a, cały rząd 1, oraz po ukosie od a1 do h8.
Drugi hetman ustawiony jest na polu c2 poza polami bicia pierwszego hetmana. Poziom pól szachownicy oznaczony jest literami od a do h, a pion od 1 do 8.

Kiedy napotkamy w końcu wiersz, w którym nie znajdziemy pola spełniającego warunki wymagane do ustawienia naszej figury (czyli takiego, które nie jest atakowane przez innego hetmana i którego kolumna jednocześnie jest wolna), musimy cofnąć się do poprzedniego wiersza i znaleźć dla niego inne wolne pole. Jeżeli tam też nie znajdziemy takiego pola, ponownie się cofamy - i tak dalej, aż do skutku.

Algorytm z nawrotami

Algorytmem z nawrotamialgorytm z nawrotamiAlgorytmem z nawrotami nazywamy taki typ algorytmu, w którym zapisywane są kolejne kroki rozwiązania. Gdy nie natrafimy na poprawne rozwiązanie, to możemy cofnąć się do poprzedniego punktu, by zmienić wcześniej podjętą decyzję. Algorytmy z nawrotami są algorytmami rekurencyjnymi. Zatem jeżeli kolejno będziemy zapisywać pozycje hetmanów, które umieściliśmy na szachownicy, a w pewnym momencie okaże się, że nasze działanie nie doprowadzi do rozwiązania (czyli nie da się umieścić kolejnego hetmana na bezpiecznej pozycji), następuje powrót do poprzedniego kroku i w danym wierszu wyszukiwane jest inne wolne pole.

Spójrzmy na poniższy rysunek przedstawiający sytuację, w której ustawiliśmy na szachownicy pięć hetmanów.

RQG5ZfYMhlkW0

Ilustracja przedstawia szachownicę z pięcioma hetmanami na polach: a1, c2, b4, d5 oraz e3.
Poza hetmanami szachownica wypełniona jest krzyżykami.
Żaden z hetmanów nie znajduje się na polu bicia reszty figur. Poziom pól szachownicy oznaczony jest literami od a do h, a pion od 1 do 8.

Znakami X oznaczone są zakresy ruchów hetmanów. Jak widzisz, nie mamy już możliwości ustawienia hetmana w szóstym wierszu. Wszystkie pola są atakowane przez inne hetmany. Musimy zatem powrócić do poprzedniego wiersza i zmienić ustawienie piątego hetmana.

R1SIqtxsiuVlj

Ilustracja przedstawia szachownicę z pięcioma hetmanami na polach: a1, c2, b4, h5 oraz e3.
Żaden z hetmanów nie znajduje się na polu bicia reszty figur.
Pola d8, d7, f7, g8 nie są polem bicia żadnej z figur. Poziom pól szachownicy oznaczony jest literami od a do h, a pion od 1 do 8.

Zmieniliśmy ustawienie, jednak dalej nie możemy ustawić hetmana w wierszu szóstym. Próbujemy znowu zmienić położenie hetmana w wierszu piątym, jednak nie mamy innych możliwości. Cofamy się więc do wiersza czwartego i szukamy dla niego innego pola.

RkXWsHWb3ktuC

Ilustracja przedstawia szachownicę z czterema hetmanami na polach: a1, c2, e3 oraz g4.
Żaden z hetmanów nie znajduje się na polu bicia reszty figur.
Pola b5, b7, b8, d8, f7, f8 oraz g8 nie są polem bicia żadnej z figur. Poziom pól szachownicy oznaczony jest literami od a do h, a pion od 1 do 8.

Hetman w wierszu czwartym przeniósł się z kolumny drugiej do kolumny siódmej. Teraz przechodzimy do kolejnego, piątego wiersza i znowu sprawdzamy, czy otrzymamy rozwiązanie problemu.

Spróbuj samodzielnie wykonać następne kroki i uzyskać układ ośmiu hetmanów na szachownicy.

Lista kroków

1. Stawiamy hetmana w pierwszym wierszu i pierwszej kolumnie.

2. Przechodzimy do kolejnego wiersza.

3. Szukamy pierwszej wolnej kolumny, tzn. takiej, która nie jest już zajęta przez innego hetmana.

4. Jeżeli znaleźliśmy takie pole, sprawdzamy, czy nie jest ono atakowane przez innego hetmana po przekątnej.

5. Jeżeli nie znaleźliśmy pola, którego kolumna jest wolna i które jednocześnie nie jest atakowane przez innego hetmana po przekątnej, wówczas z poprzedniego wiersza zdejmujemy hetmana i szukamy dla niego nowego pola (przechodzimy do punktu 3).

6. Jeżeli znaleźliśmy pole, które nie jest atakowane przez innego hetmana, ustawiamy tam hetmana.

7. Jeśli ustawiliśmy wszystkie hetmany, wypisujemy rozwiązanie – w przeciwnym wypadku przechodzimy do szukania pola dla hetmana w kolejnym wierszu (przechodzimy do punktu 2).

Słownik