Problém 8-mich dám

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 <4,7> dám

Niektoré riešenia pre 8 dám

Metóda riešenia – backtracking

Spôsob hľadania riešenia pre rôzne všeobecné problémy je tzv. metóda Backtracking (metóda pokusov a opráv, prehľadávanie s návratom, prehľadávanie do hĺbky). Jedná sa o hľadanie riešenia "hrubou silou", pretože veľké množstvo potencionálnych riešení môže byť vylúčené bez priameho vyskúšania. Princíp spočíva v tom, že celý proces sa rozloží na niekoľko čiastkových úloh, ktoré sa často vyjadrujú pomocou rekurzie a spočívajú v preskúmaní konečného počtu podúloh. Opakovaním pokusov (vyhľadávaní) sa postupne vytvorí a skúmaním zmenšuje strom podúloh. Algoritmus funguje tak, že sa zoberú do úvahy všetky možnosti, ktoré môžu viesť k vyriešeniu problému. Potom sa postupne rekurzívne riešia jednotlivé podproblémy. Množina rekurzívnych volaní vytvára stromovú štruktúru, kde je postupne kontrolovaná každá podmnožina možností. Z toho vyplýva, že ak riešenie existuje, algoritmus ho po určitom čase nájde. Backtracking je však vo všeobecnosti neefektívny prístup k riešeniu problému. Pomocou rôznych optimalizačných techník sa dá zredukovať hĺbka stromu a aj počet podstromov. Technika sa volá prehľadávanie s návratom preto, lebo po každom navštívenom liste stromu sa algoritmus vráti do zásobníka kde má uložené miesta, odkiaľ sa vnoril. Potom vyberie ďalšiu vetvu a znova sa vnorí.