Zobrazenie zdroja stránky 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í ==
{| class=wikitable border=1 cellpadding=5
|-
! 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 ==
[[Súbor:4.jpg]] [[Súbor:5.jpg]] [[Súbor:6.jpg]] [[Súbor:7.jpg]]

== Niektoré riešenia pre 8 dám ==
[[Súbor:8_1.jpg]] [[Súbor:8_2.jpg]] [[Súbor:8_3.jpg]] [[Súbor:8_4.jpg]] [[Súbor:8_5.jpg]]

== 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.