Problém osmi dam

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.

	a	b	c	d	e	f	g	h
8									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

Ú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

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í

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!/cⁿ, 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	..	227 514 171 973 736	2 207 893 435 808 352	22 317 699 616 364 044
Symetrická jen jednou^[5]	1	2	1	6	12	46	92	341	1 787	9 233	45 752	285 053		..	28 439 272 956 934	275 986 683 743 434	2 789 712 466 510 289

Přehled základních řešení

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

Jezdcova procházka

Reference

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

Externí odkazy

Obrázky, zvuky či videa k tématu problém osmi dam na Wikimedia Commons
Problém osmi dam v encyklopedii MathWorld (anglicky)
Rozsáhlá bibliografie

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.

[1] Hans Siegfried: Max Friedrich Wilhelm Bezzel Archivováno 28. 8. 2006 na Wayback Machine. na stránkách šachového oddílu Ansbach (německy)

[2] Frank Ruskey, Susan Ruskey: Information on the n Queens problem Archivováno 14. 12. 2007 na Wayback Machine., č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

[1]

[2]

[3]

[4]

[5]