V následujícím článku prozkoumáme fascinující svět Problém osmi dam. Od svého dopadu na společnost až po četné aplikace v různých oblastech, Problém osmi dam upoutal pozornost lidí všech věkových kategorií a zájmů. Ponoříme se do jeho historie, analyzujeme jeho význam dnes a prodiskutujeme možné vyhlídky do budoucna. Kromě toho podrobně prozkoumáme výhody a výzvy, které Problém osmi dam představuje, a nabídneme kompletní a vyvážený pohled na toto vzrušující téma. Přidejte se k nám na této cestě objevovat vše, co Problém osmi dam nabízí.
Problém osmi dam je šachová úloha, respektive kombinatorický problém umístit na šachovnici osm dam tak, aby se podle pravidel šachu navzájem neohrožovaly, tedy vybrat osm polí tak, aby žádná dvě nebyla ve stejné řadě, sloupci, ani diagonální linii. Obecněji jde o to nalézt všechna možná taková rozmístění nebo určit 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. Často se využívá při výuce programování, jelikož umožňuje názorný výklad backtrackingových algoritmů.
Problém osmi dam poprvé zveřejnil v berlínském časopise Schachzeitung v roce 1848 Max Bezzel. V dalších letech se problému věnovalo mnoho slavných matematiků včetně Gausse. 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 řešení úlohy pomocí determinantů, kterou poté vylepšil James Whitbread Lee Glaisher.
Problém osmi dam má 92 různých řešení (uvažují se pochopitelně jako kombinace, tedy bez vzájemného rozlišování jednotlivých dam). Těchto 92 řešení však lze získat pomocí symetrie (otočením a zrcadlením podle čtyř os) z dvanácti základních řešení – 11 má osm symetrií, jedno jen čtyři, neboť je samo středově symetrické.
Počet všech řešení problému n dam na n x n šachovnici se započtením symetrie i bez pro malá n je následující (pro n = 1 existuje jediné triviální řešení, pro 2 a 3 žádné). Existuje domněnka, že počet řešení se asymptoticky chová jako n!/cn, kde c je kolem 2,54.
Dvanáct základních řešení problému osmi dam je zobrazeno na následujících diagramech: