Problém osmi dam

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Chess zhor 26.png
Chess zver 26.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 26.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 ql h7 __
a6 __ b6 __ c6 ql d6 __ e6 __ f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 ql
a4 __ b4 ql c4 __ d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 ql f3 __ g3 __ h3 __
a2 ql b2 __ c2 __ d2 __ e2 __ f2 __ g2 __ h2 __
a1 __ b1 __ c1 __ d1 __ e1 __ f1 ql g1 __ h1 __
Chess zhor 26.png
Základní řešení vyprodukované obecným heuristickým algoritmem, začínající jako skoky jezdcem z a2 vzhůru doprava

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

Historie úlohy[editovat | editovat zdroj]

Problém osmi dam poprvé zveřejnil v berlínském časopise Schachzeitung v roce 1848 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 řešení úlohy pomocí determinantů, kterou poté vylepšil James Whitbread Lee Glaisher.[3]

Počet řešení[editovat | editovat zdroj]

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

n 4 5 6 7 8 9 10 11 12 13 14 15 16 .. 24 25 26
Všechna řešení[4] 2 10 4 40 92 352 724 2 680 14 200 73 712 365 596 2 279 184 14 772 512 .. 28 439 272 956 934 275 986 683 743 434 2 789 712 466 510 289
Symetrická jen jednou[5] 1 2 1 6 12 46 92 341 1 787 9 233 45 752 285 053 .. 227 514 171 973 736 2 207 893 435 808 352 22 317 699 616 364 044

Přehled základních řešení[editovat | editovat zdroj]

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

Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 ql h7 __
a6 __ b6 __ c6 ql d6 __ e6 __ f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 ql
a4 __ b4 ql c4 __ d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 ql f3 __ g3 __ h3 __
a2 ql b2 __ c2 __ d2 __ e2 __ f2 __ g2 __ h2 __
a1 __ b1 __ c1 __ d1 __ e1 __ f1 ql g1 __ h1 __
Chess zhor 22.png
Řešení 1
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 __ e8 ql f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 ql c7 __ d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 ql e6 __ f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 ql h5 __
a4 __ b4 __ c4 ql d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 ql
a2 __ b2 __ c2 __ d2 __ e2 __ f2 ql g2 __ h2 __
a1 ql b1 __ c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Řešení 2
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 ql c7 __ d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 ql h6 __
a5 __ b5 __ c5 ql d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 __ e4 __ f4 ql g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 ql
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 ql b1 __ c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Řešení 3
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 ql g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 ql
a5 __ b5 __ c5 ql d5 __ e5 __ f5 __ g5 __ h5 __
a4 ql b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 ql h3 __
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Řešení 4
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 ql d8 __ e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 ql g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 ql
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 ql e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 ql h3 __
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Řešení 5
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 __ e8 ql f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 ql d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 ql
a5 __ b5 __ c5 __ d5 ql e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 ql h4 __
a3 ql b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 __ f2 ql g2 __ h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Řešení 6
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 __ e8 ql f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 ql h7 __
a6 __ b6 __ c6 __ d6 ql e6 __ f6 __ g6 __ h6 __
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 ql d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 ql
a2 __ b2 __ c2 __ d2 __ e2 __ f2 ql g2 __ h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Řešení 7
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 ql b7 __ c7 __ d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 ql f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 ql
a4 __ b4 __ c4 __ d4 __ e4 __ f4 ql g4 __ h4 __
a3 __ b3 __ c3 ql d3 __ e3 __ f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 ql h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Řešení 8
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 ql d8 __ e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 ql g7 __ h7 __
a6 __ b6 __ c6 __ d6 ql e6 __ f6 __ g6 __ h6 __
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 ql
a3 __ b3 __ c3 __ d3 __ e3 ql f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 ql h2 __
a1 __ b1 ql c1 __ d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Řešení 9
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 __ e8 __ f8 ql g8 __ h8 __ Chess zver 22.png
a7 __ b7 ql c7 __ d7 __ e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 ql h6 __
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 ql e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 ql
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 __ b1 __ c1 ql d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Řešení 10
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 ql h7 __
a6 ql b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 ql
a4 __ b4 __ c4 __ d4 __ e4 ql f4 __ g4 __ h4 __
a3 __ b3 ql c3 __ d3 __ e3 __ f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 __ f2 ql g2 __ h2 __
a1 __ b1 __ c1 ql d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Řešení 11
Chess zhor 22.png
Chess zver 22.png a8 __ b8 __ c8 __ d8 __ e8 __ f8 ql g8 __ h8 __ Chess zver 22.png
a7 __ b7 __ c7 __ d7 ql e7 __ f7 __ g7 __ h7 __
a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 ql h6 __
a5 ql b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __
a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 ql
a3 __ b3 ql c3 __ d3 __ e3 __ f3 __ g3 __ h3 __
a2 __ b2 __ c2 __ d2 __ e2 ql f2 __ g2 __ h2 __
a1 __ b1 __ c1 ql d1 __ e1 __ f1 __ g1 __ h1 __
Chess zhor 22.png
Řešení 12 (středově symetrické)

Související články[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. Hans Siegfried: Max Friedrich Wilhelm Bezzel na stránkách šachového oddílu Ansbach (německy)
  2. Frank Ruskey, Susan Ruskey: Information on the n Queens problem, červen 1996, The Amazing Mathematical Object Factory (anglicky)
  3. J. J. O’Connor, E. F. Robertson: Mathematical games and recreations (anglicky)
  4. Number of ways of placing n nonattacking queens on n X n board., posloupnost A000170 v On-Line Encyclopedia of Integer Sequences
  5. Number of ways of placing n nonattacking queens on n X n board (symmetric solutions count only once), posloupnost A002562 v OEIS

Externí odkazy[editovat | editovat zdroj]