Problém 8-mich dám
Obsah
O čo vlastne ide?
Problém ôsmich dám je šachová úloha resp. kombinatorický problém kde treba umiestniť na šachovnicu osem dám tak, aby sa podľa pravidiel šachu navzájom neohrozovali.
História úlohy
Problém ôsmich dám bol prvý krát zverejnený v berlínskom časopise Schachzeitung v roku 1848 Maxom Bezzelom. V dalších rokoch sa problémom zaoberalo veľa slávnych matematikov vrátane Carla Friedricha Gaussa. Zovšeobecnenie problému na n dám navrhol v roku 1850 Franz Nauck, ktorý tiež správne stanovil počet všetkých riešení pôvodného problému. V roku 1874 navrhol Siegmund Günther metódu riešenia úlohy pomocou determinantov, ktorú neskôr vylepšil James Whitbread Lee Glaisher.
Počet riešení
Problém má 92 riešení (uvažujú sa kombinácie). Riešenia sa získavajú aj pomocou symetrie (zrkadlovým otáčaním). Je 12 základných riešení: 11 má osem symetrií, 1 iba štyri lebo je samo stredovo symetrické. Počet všetkých riešení problému n dám, započítaním symetrie aj bez nej je pre malé n takýto: pre n=1 existuje jediné triviálne riešenie, pre n=2 a n=3 neexistuje riešenie. Je domnienka, že počet riešení sa asymptoticky chová ako n!/c*n, kde c je okolo 2,54.
Tabuľka počtu riešení
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| unikátne | 1 | 0 | 0 | 1 | 2 | 1 | 6 | 12 | 46 | 92 | 341 | 1785 |
| všetky | 1 | 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2680 | 14200 |
Niektoré základné riešenia pre n dám
