Problem ośmiu hetmanów – problem polegający na wyznaczeniu liczby różnych rozmieszczeń ośmiu hetmanów na tradycyjnej szachownicy 8×8 tak, aby wzajemnie się nie atakowały. Przez rozstawienie bądź rozwiązanie podstawowe należy rozumieć takie z dokładnością do izomorfizmu, tzn. z uwzględnieniem wszystkich pokrewnych pozycji wynikających z odbić zwierciadlanych i obrotów.
Historia problemu Problem ośmiu hetmanów został po raz pierwszy sformułowany w 1848 roku przez mistrza szachowego Maksa Bezzela (1824–1871). Pierwsze rozwiązanie podał dwa lata później Franz Nauck. Również matematyk Carl Friedrich Gauss interesował się tym problemem. W roku 1992 wskazano na związki pomiędzy problemem ośmiu hetmanów a kwadratami magicznymi. W 2022 Michael Simkin z Uniwersytetu Harvarda podał przybliżony wzór na rozwiązanie problemu dla szachownicy dowolnych rozmiarów.
Sformułowanie analityczne problemu Niech (i,j) (m,n) będą współrzędnymi dwóch hetmanów dwa hetmany stoją na jednej linii wtedy i tylko wtedy gdy lub dwa hetmany stoją na jednej przekątnej wtedy i tylko wtedy gdy gdzie znak może być identyczny bądź różny w obydwu równaniach. Jak można stwierdzić, całkowita liczba rozwiązań nie może przekroczyć 8!.
Przykład rozwiązania
Charakterystyczną cechą rozwiązań jest ustawienie hetmanów w „relacji skoczka”. Podstawowych rozwiązań jest w sumie dwanaście, podstawowych, tzn. nie dających się przekształcić w siebie za pomocą odbić zwierciadlanych i obrotów. Rozwiązania te można kodować za pomocą ciągu ośmiu cyfr – w tym przypadku będzie to [41582736]. Interesującą własnością powyższego rozwiązania jest jego rozszerzalność – korzystając z „nieobłożenia” głównej przekątnej, można dodać hetmana na polu i9, rozszerzając przy tym szachownicę do rozmiaru 9×9.
Jedyne rozwiązanie symetryczne
Oto drugie z rozwiązań [46827135]. Jako jedyne posiada środek symetrii (obrót szachownicy o 180 stopni prowadzi do tego samego układu). Wynika stąd liczba możliwych rozwiązań 92, a nie 96:
Podstawowych rozwiązań jest 12, symetrii natomiast 8: odbicie w poziomie odbicie w pionie dwa odbicia względem głównych przekątnych cztery obroty (o 0, 90, 180 i 270 stopni)
Zatem wszystkich rozwiązań powinno być Jest ich 92, bowiem dla tego rozwiązania symetrycznego: odbicie w poziomie jest równoważne odbiciu w pionie,i odbicie względem jednej przekątnej jest równoważne odbiciu względem drugiej przekątnej, obrót o 0 stopni jest równoważny obrotowi o 180 stopni, obrót o 90 stopni jest równoważny obrotowi o 270 stopni.
Dwa powyższe rozwiązania są jedynymi rozwiązaniami, w których hetmany stoją poza głównymi przekątnymi.
Rozwiązanie łatwe do zapamiętania
Rozwiązanie łatwe do zapamiętania dzięki regularności, która nie jest symetrią.
Dwanaście rozwiązań podstawowych Oto wszystkie dwanaście istniejących rozwiązań zakodowanych za pomocą cyfr oznaczających położenie hetmana na konkretnej kolumnie: {41582736} {41586372} {42586137} {42736815} {42736851} {42751863} {42857136} {42861357} {46152837} {46827135} {47526138} {48157263}
Tabelka liczb rozwiązań W poniższej tabelce można znaleźć liczby możliwych ustawień dla szachownic o innym rozmiarze. Liczba rozwiązań dla szachownicy o rozmiarze wynosi ok. . n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 rozwiązań podstawowych 1 0 0 1 2 1 6 12 46 92 341 1 787 9 233 45 752 285 053 1 846 955 11 977 939 83 263 591 rozwiązań wszystkich 1 0 0 2 10 4 40 92 352 724 2 680 14 200 73 712 365 596 2 279 184 14 772 512 95 815 104 666 090 624
Szachownice o innym wymiarze Analogiczny problem dla szachownicy 5×5
Problem posiada dwa rozwiązania podstawowe: [25314] – rozwiązanie symetryczne [14253] – rozwiązanie asymetryczne
Ze względu na liczbę symetrii, mianowicie 8, można by przypuszczać, iż wszystkich rozwiązań będzie 16. W istocie jest ich 10.
gdzie 4 oznacza liczbę symetrii pierwszego rozwiązania
Analogiczny problem dla szachownicy 6×6 [531642] – jedyne rozwiązanie
Problem posiada jedno rozwiązania podstawowe. Ze względu na liczbę symetrii, mianowicie 8, można by przypuszczać, iż wszystkich rozwiązań jest 8. W istocie rzeczy są 4 rozwiązania.
gdzie 2 oznacza liczbę symetrii jakie posiada jedyne rozwiązanie podstawowe.
Analogia wieżowa Jeśli zastąpić hetmany wieżami, rozwiązań jest więcej. W istocie jest ich n! gdzie n jest rozmiarem szachownicy. Rozwiązań podstawowych jest jednak znacznie mniej, ze względu na linie symetrii pojawiające się w konfiguracjach.
I tak na przykład na szachownicy 4×4 mamy 24 rozwiązania redukujące się do siedmiu rozwiązań podstawowych, mianowicie:
Na klasycznej szachownicy 8×8 rozwiązań jest 8!=40320, redukujących się do 5282 rozwiązań podstawowych.
Zobacz też matematyka i szachy problem czterech hetmanów
Przypisy
Bibliografia Marek Zawadowski Wykład ze wstępu do informatyki.
Linki zewnętrzne Impresje na temat problemu n-królowych
Kategoria:Rozrywka matematyczna Kategoria:Szachy Kategoria:Problemy matematyczne