Problém osmi dam

Jedno možné řešení

Problém osmi dam je úloha umístit na prázdnou šachovnici osm dam tak, aby se podle běžných pravidel šachu žádné dvě navzájem neohrožovaly, tedy tak, aby žádné dvě dámy nebyly na stejné řadě, sloupci, ani diagonále, případně nalézt všechna možná řešení této úlohy (nebo jejich počet).

Úlohu lze zobecnit na problém n dam, tedy otázku, jak lze rozmístit n dam na šachovnici o rozměrech n×n tak, aby se vzájemně neohrožovaly.

[editovat] Historie úlohy

Problém osmi dam se poprvé objevil v roce 1848, kdy ho v berlínském časopise Schachzeitung uveřejnil Max Bezzel.^[1] V dalších letech se problému věnovalo mnoho slavných matematiků včetně Gausse.^[2] Zobecnění problému na n dam navrhl v roce 1850 Franz Nauck (který také správně stanovil počet všech řešení původního problému). V roce 1874 navrhl Siegmund Günther metodu pro řešení úlohy pomocí determinantů, kterou poté vylepšil James Gleisher.^[3]

[editovat] Počet řešení

Problém osmi dam má 92 různých řešení (až na permutace rozmístěných dam, tzn. pokud se zvažují jen pole, na která se dámy umísťují, nikoli konkrétní figurky na konkrétních polích). Těchto 92 řešení však lze získat z dvanácti různých řešení pomocí symetrie (otočením a zrcadlením).

Při zobecnění na problém n dam je počet všech řešení, resp. řešení se započtením symetrie, pro malá n uveden v následující tabulce:

[editovat] Přehled řešení problému osmi dam

Dvanáct základních řešení problému osmi dam je zobrazeno na následujících diagramech:

__	__	__	__
__	__