Problem ośmiu hetmanów

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Problem ośmiu hetmanówhetman jest figurą szachową, która bije figury znajdujące się w tej samej kolumnie, wierszu lub przekątnej, co on sam. W jaki sposób rozstawić osiem hetmanów na tradycyjnej szachownicy 8x8 tak, aby wzajemnie się nie atakowały? Ile jest możliwych rozstawień? Przez rozstawienie podstawowe bądź rozwiązanie podstawowe należy rozumieć rozwiązanie 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 i=m lub j=n
  • dwa hetmany stoją na jednej przekątnej wtedy i tylko wtedy gdy i=m\pm x, j=n\pm x

gdzie znak x\; 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]

Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png


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 9x9.

Jedyne rozwiązanie symetryczne[edytuj | edytuj kod]

Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png


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ć 96=12x8. 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.

Co ciekawe 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]

Chess zhor 22.png
Chess zver 22.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 22.png
Chess zhor 22.png


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 5x5

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.

  • 10 = (8/4) + 8

gdzie 4 oznacza ilość symetrii pierwszego rozwiązania

Analogiczny problem dla szachownicy 6x6

  • [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.

  • 4 = (8/2)

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 4x4 mamy 24 rozwiązania redukujące się do siedmiu rozwiązań podstawowych, mianowicie:

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

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

Bibliografia[edytuj | edytuj kod]

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]