Problem ośmiu hetmanów

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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]

a b c d e f g h
8
Chessboard480.svg
e8 white queen
c7 white queen
a6 white queen
f5 white queen
h4 white queen
b3 white queen
d2 white queen
g1 white queen
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 i0 rozszerzając przy tym szachownicę do rozmiaru 9x9.

Jedyne rozwiązanie symetryczne[edytuj | edytuj kod]

a b c d e f g h
8
Chessboard480.svg
f8 white queen
d7 white queen
g6 white queen
a5 white queen
h4 white queen
b3 white queen
e2 white queen
c1 white queen
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=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]

a b c d e f g h
8
Chessboard480.svg
d8 white queen
g7 white queen
c6 white queen
h5 white queen
b4 white queen
e3 white queen
a2 white queen
f1 white queen
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[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.

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]