8 Hetmanów

Cel

Na standardowej szachownicy 8×8 ustaw osiem hetmanów tak, aby siebie nie atakowały. Ile jest możliwych takich ustawień? Ile jest ustawień unikalnych tj. nie powstałe przez odbicie lub obrót innego?

Szachownica

Ruch Hetmana

Hetman może poruszać się pionowo, poziomo oraz na ukos czyli w dowolnym kierunku o dowolną ilość pól. Każde pole na którę może przesunąć się hetman jest polem atakowanym.

Implementacja

Założenia

Problem ośmiu hetmanów można przenieść na szachownicę dowolnej wielkości i rozważać ile jest możliwych ustawień. Jednak do coraz większych plansz może przydać się program komputerowy, który o wiele szybciej policzy szukaną wartość.

Standardowy sposób szukania wszystkich możliwych ustawień wykorzystuje zadeklarowanie dwuwymiarowej tablicy, a następnie odpowiednio zaznaczenie zajętych pozycji, a następnie sprawdzanie, gdzie można ustawić kolejne hetmany. Istnieje jednak prosty sposób na optymalizację rozwiązywania tego problemu.

Idea

Pewne jest, że pole na którym został ustawiony hetman jednoznacznie identyfikuje jego pozycja (x, y). Jednak wiadomo, że każdy kolejny hetman występuje w kolejnym wierszu (lub kolumnie zależy od spojrzenia). Oznacza to jednak, że jeśli zapiszemy numer kolumny (wiersza) każdego kolejnego hetmana to znamy też wiersz (kolumnę) jego pozycji na podstawie pozycji w ciągu.

Przykładowo kod 47526138 oznacza, że pierwszy hetman jest na pozycji (1, 4), a kolejny na (2, 7) itd. Aktualizacja takiego kodu w trakcie wykonywania jest proste i zdecydowanie oszczędza pamięć. Złożoność takiego rozwiązania jest O(n), a nie O(n²) (jeśli deklarowana jest tablica 2D danych).

Sposób działa algorytmu gwarantuje, że dwa hetmany nie wystąpią w tym samym wierszu. Sprawdzenie czy nie wystąpią dwa hetmany w tej samej kolumnie sprowadza się do sprawdzenia odpowiedniej współrzędnej. Pozostaje jednak kwestia ataków ukośnych. Z pomocą przychodzi matematyka. Dwa hetmany będą się atakować po skosie jeśli różnica między wartością absolutną przesunięcia wzdłuż osi X jak i Y są sobie równe.

Rozwiązanie

Funkcja ustawHetmana() przyjmuje dwa argumenty: dane - aktualny kod planszy oraz n - wielkość planszy.

1. int ustawHetmana(vector<int> &dane, int n) {
2.   int ile = 0;
3.   if (dane.size() == n) {
4.     return 1;
5.   } else {
6.     for (int k = 0; k < n; k++) {
7.       if (czyMoze(dane, dane.size(), k)) {
8.         dane.push_back(k);
9.         ile += ustawHetmana(dane, n);
10.         dane.pop_back();
11.       }
12.     }
13.   }
14.   return ile;
15. }

Rozwiązanie jest wyszukiwane rekurencyjnie. W każdym kolejnym kroku w kolejnym wierszu sprawdzane są wszystkie pola, gdzie można postawić bierkę. Następnie po postawieniu algorytm przechodzi do kolejnego wiersza. Warunkiem stopu jest uzyskanie kodu o tylu znakach jaki jest rozmiar tablicy n.

W celu wykrycia czy na polu (x, y) można postawić hetmana funkcja korzysta z funkcji czyMoze(), która sprawdza czy przekazana pozycja koliduje z którąś z aktualnych pozycji zapisanych w kodzie dane.

1. bool czyMoze(vector<int> &dane, int x, int y) {
2.   for (int i = 0; i < dane.size(); i++) {
3.     int przesx = abs(i - x);
4.     int przesy = abs(dane[i] - y);
5.     if (dane[i] == y || przesx == przesy)
6.       return false;
7.   }
8.   return true;
9. }

Jeszcze potrzebna jest funkcja szukajRozwiazan(), który przygotowuje pustą listę na zapis kodu, a następnie uruchamia poszukiwanie rozwiązań.

1. int szukajRozwiazan(int n) {
2.   vector<int> dane;
3.   return ustawHetmana(dane, n);
4. }

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu kodu, który wczyta od użytkownika na jakim rozmiarze planszy mają zostać wyszukane możliwe rozwiązania.

1. int main() {
2.   int n;
3.   cout << "Podaj wielkosc planszy\n n = ";
4.   cin >> n;
5.   cout << "Rozwiazan: " << szukajRozwiazan(n);
6.   system("pause");
7.   return 0;
8. }

• Kod źródłowy Implementacja