Problem ośmiu hetmanów

Problem ośmiu hetmanów – hetman 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

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

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

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

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,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,
• obbicie 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

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

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

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

• Marek Zawadowski Wykład ze wstępu do informatyki.

Zobacz też

• problem czterech hetmanów
• matematyka i szachy

Linki zewnętrzne

• Impresje na temat problemu n-królowych