Úkolem problému s osmi dámami je umístit osm šachů ze šachové partie na šachovnici čtvercového formátu 8 × 8, aniž by se šachy mohly navzájem vyhrožovat, v souladu s pravidly šachové hry (barva figurek být ignorován). Dvě dámy by proto nikdy neměly sdílet stejný řádek, sloupec nebo úhlopříčku. Tento problém patří do oblasti matematických úloh, nikoli do oblasti šachové kompozice .
Jednoduché, ale ne triviální, tento problém se často používá jako příklad pro ilustraci programovacích technik .
Po celá léta mnoho matematiků , včetně Gaussa , pracovalo na tomto problému, což je zvláštní případ zobecněného problému n -dames, který v roce 1850 představil Franz Nauck, a který má umístit na šachovnici n "svobodné" dámy. n × n políček. V roce 1874 S. Gunther navrhl metodu hledání řešení pomocí determinantů a JWL Glaisher tento přístup vylepšil.
Tento problém byl použit na počátku 90. let ve hře na PC The 7th Guest ( Seventh asked ).
Problém s osmi dáma má 92 odlišných řešení, nebo pouze 12 řešení zohledňujících transformace, jako jsou rotace nebo odrazy (prostřednictvím Burnsideova lemmatu ). Všimněte si, že jedním z pozoruhodných řešení bez ohledu na velikost šachovnice je to
Každá královna má svou symetrii v sousedním sloupci, kromě těch 2, které se dotýkají vodorovné osy symetrie šachovnice (jedinečné řešení 5) |
|
||
|
||
|
||
|
Na tradiční šachovnici může být uspořádáno čtrnáct biskupů , třicet dva rytířů nebo šestnáct králů, aniž by jakýkoli kousek ohrožoval jiný. Tyto pohádkové šachové figurky mohou nahradit dámy.
Pólya studovala problém n- šachovnic na toroidní šachovnici . Byly použity další podpěry, například trojrozměrné šachovnice.
Problémem je najít minimální počet královen (nebo jiných figurek) nezbytných pro ovládání všech čtverců šachovnice n × n . Například u šachovnice „8 × 8“ má toto číslo hodnotu pět.
Snažíme se umístit devět královen a pěšce na klasickou šachovnici, abychom zabránili zachycení královen. Tento problém je zobecněn zvážením šachovnice n × n a r královen ( r > n ) a je nutné najít minimální počet figurek, aby mohly být královny a figurky umístěny na šachovnici, aniž by se královny navzájem vyhrožovaly .
V roce 1992 Demirörs, Rafraf a Tanik zveřejnili metodu převodu magických čtverců na řešení problému n- checkers a naopak.
Problém osmi dám je dobrým příkladem jednoduchého, ale ne zjevného problému. Z tohoto důvodu se často používá jako implementace podpory různých programovacích technik, včetně netradičních přístupů k programování, jako je programování omezení , programovací logika nebo genetické algoritmy .
Nejčastěji se používá jako příklad problému, který lze vyřešit rekurzivním algoritmem , vyjádřením, že řešení problému n -dames lze získat indukcí z libovolného řešení problému des ( n -1 ) -dames přidáním dámy. Opakování začíná řešením problému 0-královna, který spočívá na prázdné šachovnici.
Tato technika je mnohem efektivnější než naivní vyčerpávající vyhledávací algoritmus , který prochází každým z 64 8 = 2 48 = 281 474 976 710 656 možných umístění osmi královen, aby odstranil všechna ta, pro která je několik královen na stejném čtverci. (ponechává pouze 178 462 987 637 760 možných opatření ) nebo pro které se dámy navzájem vyhrožují.
S ohledem na složitost algoritmu tento velmi „špatný“ algoritmus vyprodukuje několikrát stejné výsledky přiřazením různých míst osmi dámám a několikrát zopakuje stejné výpočty pro různé části každého řešení. Mírně lepší vyčerpávající vyhledávací algoritmus umisťuje jednu královnu na řádek, čímž se snižuje pouze na 8 8 = 2 24 = 16 777 216 možných umístění.
Je možné udělat mnohem lépe než to. Například hloubkový výzkumný program by se podíval na pouhých 15 720 možných umístění dám tím, že vytvoří výzkumný strom a jeden po druhém prochází řadami šachovnice, což eliminuje většinu možných pozic ve velmi primitivní fázi jejich konstrukce. .
Programování omezení je mnohem účinnější pro tento problém. Algoritmus „iterativní opravy“ obvykle začíná umístěním všech královen na šachovnici, například pouze s jednou královnou na sloup. Poté spočítá počet konfliktů mezi dámami a pomocí heuristické metody určí, jak zlepšit umístění dám. Obzvláště účinná je heuristická metoda nejmenšího konfliktu, která spočívá v přesunutí části s největším počtem konfliktů ve stejném sloupci na místo, kde je nejnižší počet konfliktů. Řeší problém milionů dám (na šachovnici 1 000 000 × 1 000 000 čtverců) v průměru za méně než 50 kroků .
Získání tohoto průměru o 50 krocích předpokládá, že počáteční nastavení je přiměřeně dobré. Pokud je na začátku do stejné řady umístěno milion dám, algoritmus zjevně podnikne více než 50 kroků k vyřešení problému. „Přiměřeně dobrým“ výchozím bodem je umístění každé královny do sloupce tak, aby byla v konfliktu s nejmenším počtem královen, které jsou již na palubě.
Metoda iterativní opravy, na rozdíl od hloubkového výzkumu popsaného výše, nezaručuje řešení. Stejně jako všechny metody hlubšího sestupu se může zaseknout v místním extrému (v tomto případě lze algoritmus restartovat s jinou počáteční konfigurací.) Na druhou stranu může vyřešit velké problémy, které jsou daleko za rámec -hloubkový výzkum.