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

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

Przykład rozwiązania

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

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

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

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=12*8.$ 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

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

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 $n$ wynosi ok. $(0,143n)^{n}$.

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.

• $10={\frac {8}{4}}+8$

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.

• $4={\frac {8}{2}}$

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:

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

• matematyka i szachy
• problem czterech hetmanów

Bibliografia

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

Linki zewnętrzne

• Impresje na temat problemu n-królowych