Problem 8 hetmanów

Z Wikipedii

Problem 8 hetmanów - hetman jest figurą szachową, która bije figury znajdujące się w tej samej kolumnie, wierszu lub diagonali 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 przekształceń o charakterze symetrii i obrotów.

[edytuj] Historia problemu

Problem ośmiu hetmanów został po raz pierwszy sformułowany w 1848 roku przez mistrza szachowego nazwiskiem Max Bezzel (1824-1871). Pierwsze rozwiązanie podał dwa lata później Franz Nauck. Również matematyk Carl Friedrich Gauss interesował się tym problemem, jednak nie on jako pierwszy. W roku 1992 wskazano na związki pomiędzy problemem ośmiu hetmanów a kwadratami magicznymi.

[edytuj] 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 diagonali wtedy i tylko wtedy gdy i=m+x i j=n+x

gdzie wartość +x może być ujemna lub dodatnia niezależnie w obu równaniach. Jak można stwierdzić całkowita ilość rozwiązań nie może przekroczyć 8!.

[edytuj] 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 wynikających z symetrii zwierciadlanej bądź rotacyjnej. 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 'ekstensywność' - korzystając z 'nieobłożenia' głównej przekątnej można dodać hetmana na polu i0 rozszerzając przy tym szachownicę do wymiaru 9x9.

[edytuj] Jedyne rozwiązanie symetryczne

Oto drugie z rozwiązań [46827135]. Jest najciekawsze bo symetryczne. Obrót szachownicy o 180 stopni nie powoduje zmiany. Jest to bezpośrednia przyczyna dlaczego wszystkich możliwych rozwiązań jest 92 a nie 96. Podstawowych rozwiązań jest 12, symetrii natomiast 8:

symetria horyzontalna
symetria wertykalna
dwie symetrie wg głównych diagonali
cztery symetrie rotacyjne (0,90,180,270 stopni)

Zatem wszystkich rozwiązań powinno być 96=12x8. Jest ich 92 bowiem przekształcenie wg symetrii horyzontalnej jest równoznaczne z przekształceniem wg symetrii wertykalnej, przekształcenie wg symetrii jednej diagonali jest równoważne z przekształceniem wg symetrii drugiej diagonali, symetria rotacyjna 0 stopni jest równoważna symetrii rotacyjnej 180 stopni, symetria rotacyjna 90 stopni jest równoważne symetrii rotacyjnej 270 stopni.

Co ciekawe dwa powyższe rozwiązania są jedynymi rozwiązaniami, w których hetmany stoją poza głównymi przekątnymi.

[edytuj] Rozwiązanie łatwe do zapamiętania

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

[edytuj] 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 wertykali:

{ 41582736 }
{ 41586372 }
{ 42586137 }
{ 42736815 }
{ 42736851 }
{ 42751863 }
{ 42857136 }
{ 42861357 }
{ 46152837 }
{ 46827135 }
{ 47526138 }
{ 48157263 }

[edytuj] 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 mniej więcej eksponencjalnie, nie jest jednak znany konkretny 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

[edytuj] Szachownice o innym wymiarze

Analogiczny problem dla szachownicy 5x5

[25314] - rozwiązanie pierwsze symetryczne
[14253] - rozwiązanie drugie asymetryczne

Problem posiada dwa rozwiązania podstawowe. Ze względu na ilość symetrii, mianowicie 8, można by przypuszczać iż wszystkich rozwiązań jest 16. W istocie rzeczy 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 ilość 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.

[edytuj] 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, a to 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.

[edytuj] Bibliografia

Marek Zawadzki Wykład ze wstępu do informatyki.

[edytuj] Zobacz też

problem 4 hetmanów

Kategorie: Rozrywka matematyczna • Szachy

See also ebooksgratis.com: no banners, no cookies, totally FREE.