Problém osmi dam

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
a b c d e f g h
8
Chessboard480.svg
d8 bílý dáma
g7 bílý dáma
c6 bílý dáma
h5 bílý dáma
b4 bílý dáma
e3 bílý dáma
a2 bílý dáma
f1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
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:

a b c d e f g h
8
Chessboard480.svg
d8 bílý dáma
g7 bílý dáma
c6 bílý dáma
h5 bílý dáma
b4 bílý dáma
e3 bílý dáma
a2 bílý dáma
f1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Řešení 1
a b c d e f g h
8
Chessboard480.svg
e8 bílý dáma
b7 bílý dáma
d6 bílý dáma
g5 bílý dáma
c4 bílý dáma
h3 bílý dáma
f2 bílý dáma
a1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Řešení 2
a b c d e f g h
8
Chessboard480.svg
d8 bílý dáma
b7 bílý dáma
g6 bílý dáma
c5 bílý dáma
f4 bílý dáma
h3 bílý dáma
e2 bílý dáma
a1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Řešení 3
a b c d e f g h
8
Chessboard480.svg
d8 bílý dáma
f7 bílý dáma
h6 bílý dáma
c5 bílý dáma
a4 bílý dáma
g3 bílý dáma
e2 bílý dáma
b1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Řešení 4
a b c d e f g h
8
Chessboard480.svg
c8 bílý dáma
f7 bílý dáma
h6 bílý dáma
a5 bílý dáma
d4 bílý dáma
g3 bílý dáma
e2 bílý dáma
b1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Řešení 5
a b c d e f g h
8
Chessboard480.svg
e8 bílý dáma
c7 bílý dáma
h6 bílý dáma
d5 bílý dáma
g4 bílý dáma
a3 bílý dáma
f2 bílý dáma
b1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Řešení 6
a b c d e f g h
8
Chessboard480.svg
e8 bílý dáma
g7 bílý dáma
d6 bílý dáma
a5 bílý dáma
c4 bílý dáma
h3 bílý dáma
f2 bílý dáma
b1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Řešení 7
a b c d e f g h
8
Chessboard480.svg
d8 bílý dáma
a7 bílý dáma
e6 bílý dáma
h5 bílý dáma
f4 bílý dáma
c3 bílý dáma
g2 bílý dáma
b1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Řešení 8
a b c d e f g h
8
Chessboard480.svg
c8 bílý dáma
f7 bílý dáma
d6 bílý dáma
a5 bílý dáma
h4 bílý dáma
e3 bílý dáma
g2 bílý dáma
b1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Řešení 9
a b c d e f g h
8
Chessboard480.svg
f8 bílý dáma
b7 bílý dáma
g6 bílý dáma
a5 bílý dáma
d4 bílý dáma
h3 bílý dáma
e2 bílý dáma
c1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Řešení 10
a b c d e f g h
8
Chessboard480.svg
d8 bílý dáma
g7 bílý dáma
a6 bílý dáma
h5 bílý dáma
e4 bílý dáma
b3 bílý dáma
f2 bílý dáma
c1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Řešení 11
a b c d e f g h
8
Chessboard480.svg
f8 bílý dáma
d7 bílý dáma
g6 bílý dáma
a5 bílý dáma
h4 bílý dáma
b3 bílý dáma
e2 bílý dáma
c1 bílý dáma
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Ř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]