Problem ośmiu hetmanów

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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 | edytuj kod]

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.

Sformułowanie analityczne problemu[edytuj | edytuj kod]

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 ilość rozwiązań nie może przekroczyć 8!.

Przykład rozwiązania[edytuj | edytuj kod]

ABCDEFGH
8
Chessboard480.svg
E8 – Biały hetman
C7 – Biały hetman
A6 – Biały hetman
F5 – Biały hetman
H4 – Biały hetman
B3 – Biały hetman
D2 – Biały hetman
G1 – Biały hetman
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 i0, rozszerzając przy tym szachownicę do rozmiaru 9×9.

Jedyne rozwiązanie symetryczne[edytuj | edytuj kod]

ABCDEFGH
8
Chessboard480.svg
F8 – Biały hetman
D7 – Biały hetman
G6 – Biały hetman
A5 – Biały hetman
H4 – Biały hetman
B3 – Biały hetman
E2 – Biały hetman
C1 – Biały hetman
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,
  • 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 | edytuj kod]

ABCDEFGH
8
Chessboard480.svg
D8 – Biały hetman
G7 – Biały hetman
C6 – Biały hetman
H5 – Biały hetman
B4 – Biały hetman
E3 – Biały hetman
A2 – Biały hetman
F1 – Biały hetman
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 | edytuj kod]

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 | edytuj kod]

W poniższej tabelce można znaleźć liczby możliwych ustawień dla szachownic o innym rozmiarze. Liczba rozwiązań rośnie w przybliżeniu wykładniczo, nie jest jednak znany ogólny wzór podający ową liczbę.

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 | edytuj kod]

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 ilość 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 ilość symetrii jakie posiada jedyne rozwiązanie podstawowe.

Analogia wieżowa[edytuj | edytuj kod]

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 | edytuj kod]

Bibliografia[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]