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). Prawidłowa odpowiedź została określona dwa lata później przez Franza Naucka. Również matematyk Carl Friedrich Gauss interesował się tym problemem, jednak nie on jako pierwszy. W roku 1992 wykazano ekwiwalencję 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 rozwiazań 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.
zobacz także: problem 4 hetmanów
[edytuj] Bibliografia
- Marek Zawadzki Wykład ze wstępu do informatyki.
