Problém osmi královen

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 26. ledna 2022; kontroly vyžadují 2 úpravy .

Problém osmi dam je známým kombinatorickým problémem pro uspořádání figurek na šachovnici . Počáteční formulace: "Uspořádejte 8 dam na standardní 64článkové šachovnici tak, aby žádná z nich nebyla napadena jinou . " Rozumí se, že královna porazí všechny buňky umístěné podél vertikál, horizontál a obou diagonál.

Zobecněním problému je umístit královny stejným způsobem na libovolné obdélníkové pole, zejména čtvercové se stranou . $n$

Formulace

Přísně matematicky lze problém formulovat několika způsoby, například takto: „Naplňte matici nulami a jedničkami tak , aby součet všech prvků matice byl roven 8, přičemž součet prvky v žádném sloupci, řádku nebo diagonálním řádku matice nepřesahují jednu.“ $8\times 8$

Konečný cíl stanovený pro řešitele problému lze formulovat několika způsoby:

Sestavte libovolné řešení problému.
Analyticky dokažte, že řešení existuje .
Určete počet řešení.
Sestavte všechna možná řešení.
Napište počítačový program, který najde všechna možná řešení problému. Jeden z typických úkolů pro programování výčtových algoritmů .

Někdy vyjádření problému vyžaduje najít způsoby, jak uspořádat královny na desce buněk (všimněte si, že problém nemá řešení). $N$ $N \krát N$ $1<N<4$

Vlastnosti řešení

Celkový počet možných uspořádání 8 dam na 64článkové desce je ( kombinační vzorec ). Celkový počet možných uspořádání, která splňují podmínky problému, je 92. Sada těchto 92 uspořádání je rozdělena do 12 podmnožin (11 podmnožin po 8 uspořádáních a jedno ze čtyř zbývajících), v každé z nich jsou všechna uspořádání získané od sebe transformacemi symetrie: odrazy od vertikální a horizontální osy, odrazy od úhlopříček desky a rotace o 90, 180 a 270 stupňů. $4\,426\,165\,368={\dfrac {64!}{8!\,(64-8)!}}$

Moderní počítače již umožňují řešení problému (nalézání některého nebo všech řešení) vyčerpávajícím výčtem všech možných možností uspořádání, ale takové řešení je obvykle považováno za nesprávné: řešitel problému musí najít algoritmus, který by výrazně snížil množství výčtu. . Například je zřejmé, že na jedné vodorovné nebo svislé desce nemůže být více než jedna dáma, takže algoritmus řešení by zpočátku neměl zahrnovat do hledání pozice, kde jsou dvě dámy na stejné horizontální nebo vertikální rovině. I takto jednoduché pravidlo může výrazně snížit počet možných umístění: místo 4 426 165 368 . Generováním permutací, které jsou řešením problému osmi věží, a následnou kontrolou útoků podél diagonál můžeme snížit počet možných uspořádání na pouhých . Pokud se při generování pozic vezme v úvahu i podmínka diagonálního útoku, pak se rychlost počítání řádově zvýší a počet cyklů pro vyřešení problému bude 4022. $16\,777\,216=8^{8}$ $40\,320=8!$

Jedním z typických algoritmů pro řešení problému je použití backtrackingu : první dáma je umístěna na první horizontálu, pak každá další je umístěna na další, aby nebyla poražena dříve stanovenými dámami. Pokud v další fázi nastavení nejsou žádná volná pole, dojde ke kroku zpět - dříve nastavená dáma je přeskupena.

Poznámky

Odkazy

Fraktální řešení úlohy pro desky , jestliže N=(a1)•(a2)•…•(an), kde a1 ≥ 4 a a2,…,an > 4 (A. Ermakov, 2011) $N \krát N$
Obecná metoda n queens s implementací java