Problem ośmiu hetmanów

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 edytuj

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[1].

Sformułowanie analityczne problemu edytuj

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 edytuj

abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh

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 edytuj

abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh

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 edytuj

abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh

Rozwiązanie łatwe do zapamiętania dzięki regularności, która nie jest symetrią.

Dwanaście rozwiązań podstawowych edytuj

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ń edytuj

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.  [1].

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 edytuj

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 edytuj

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:

  • [1234] [2134] [3214] [1324] [3241] [3421] [3142]

Na klasycznej szachownicy 8×8 rozwiązań jest 8!=40320, redukujących się do 5282 rozwiązań podstawowych.

Zobacz też edytuj

Przypisy edytuj

  1. a b A different kind of queen’s gambit. harvard.edu. [dostęp 2022-03-30]. (ang.).

Bibliografia edytuj

Linki zewnętrzne edytuj