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 ďalší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í.

Algoritmus backtrackingu

1. k:=1; a[0] := Ø; {Vektor Ø je prázdny}

2. IF V[k] = Ø THEN pokračuj bodom 8; {Vo V[k] nie sú ďalší kandidáti}

3. Vyber a[k] z V[k]; V[k] := V[k] - {a[k]}; {Z V[k] vybrať ďalšieho kandidáta}

4. a[k] := a[k-1] a[k]; {Vektor a[k-1] je predĺžený o 1 prvok}

5. IF k >= n THEN Vypíš riešenie; Koniec

6. k := k + 1; {Prechod k ďalšiemu predĺženiu}

7. Pokračuj krokom 2;

8. k := k - 1; {Odstránenie posledného predĺženia}

9. IF k=0 THEN Vypíš "Riešenie neexistuje";Koniec

10. Pokračuj krokom 2;

Formulácia

Problém označme ako P. Predpokladajme, že riešením problému má byť vektor a[n] = (a[1], a[2], ..., a[n]), ktorý spĺňa určitú vlastnosť, ktorú označme ako A. Vo všeobecnosti platí, že i-tá položka tohoto vektora bola vybratá z množiny povolených hodnôt V[i], t.j. a[i] z V[i] pre i= 1, 2, ..., n. Vektor a[n] má n, pre n=1, 2, ..., prvkov a je postupne predlžovaný, t.j. pre n=1 má jeden prvok, pre n=2 dva prvky, atď. Jedna možnosť ako vyriešiť problém P by bolo vyskúšať všetky možnosti (použiť "hrubú silu"), ale to by viedlo k prevereniu |V[1]|*|V[2]|*... *|V[n]| vektorov. Metóda prehľadávania s návratom umožňuje ušetriť skúmanie niektorých vektorov, pretože vektor riešenia je konštruovaný postupne a predlžovaný v súlade s vlastnosťou A. Predĺženie je vždy najprv skontrolované a je možné len vtedy, ak nebude porušená vlastnosť A.

Použité zdroje

[1] Problém osmi dam. Dostupné: <http://cs.wikipedia.org/wiki/Problém_osmi_dam>

[2] Backtracking. Dostupné: <http://cs.wikipedia.org/wiki/Backtracking>

[3] Andrejková, G.: Metóda prehľadávanie s návratom (Backtrack). Dostupné: <http://ics.upjs.sk/~novotnyr/home/skola/programovanie_a_algoritmy/10tyzden.doc>

[4] Backtracking. Dostupné: <http://www.sprite.edi.fmph.uniba.sk/~szorad/Zaklady/Backtracking.html>