Achtdamesprobleem

Het achtdamesprobleem is een schaakprobleem waarbij acht dames zodanig op een schaakbord van 8×8 velden moeten worden geplaatst dat ze elkaar volgens de schaakregels niet aanvallen of dekken. Dit betekent dat twee dames niet in dezelfde kolom, rij of diagonaal kunnen staan. Het achtdamesprobleem is een voorbeeld van het meer algemene $n$ -damesprobleem, waarbij $n$ dames op een $n\times n$ schaakbord geplaatst moeten worden. Voor $n=2$ en $n=3$ kunnen er $n-1$ dames op het bord geplaatst worden, voor grotere $n$ kunnen $n$ dames geplaatst worden.^[1]^[2]

Geschiedenis

Het probleem werd oorspronkelijk in 1848 geformuleerd door de schaker Max Bezzel. Jarenlang werd door verscheidene wiskundigen aan het probleem gewerkt. Als eerste noemde Franz Nauck het correcte aantal oplossingen in 1850: 92.^[3]^[4] Na de publicatie hebben vele wiskundigen, inclusief Carl Friedrich Gauss, zich met het probleem beziggehouden. Reeds in september 1850 publiceerde Nauck alle 92 oplossingen voor dit probleem, maar gaf geen bewijs dat dit alle oplossingen waren. Gauss heeft in detail beschreven hoe zo'n bewijs er zou moeten uitzien, maar heeft het nooit toegepast, ook al beweerde Gauss dat het "maar een uur of twee in beslag zou nemen".^[5]

De Engelse wiskundige James W. L. Glaisher stelde in 1874 voor om ook het meer algemene $n$ -damesprobleem te onderzoeken.^[6] Datzelfde jaar bewees Pauls dat de oplossing van Nauck volledig was: er bestaan niet meer dan 92 oplossingen.^[7]^[8]

Edsger Dijkstra nam in 1972 het achtdamesprobleem als voorbeeld om de voordelen van gestructureerd programmeren mee te laten zien.^[9]^[10] Hij gebruikte bij zijn backtracking de methode van depth-first search.

Oplossingen

Er zijn wanneer de namen van de velden in acht worden genomen 92 mogelijkheden om de acht dames op het schaakbord te plaatsen. Wanneer de namen van de velden niet tellen, zijn er twaalf oplossingen. Het verschil zit erin dat dan door draaien en spiegelen twee van de 92 oplossingen hetzelfde kunnen zijn. De twaalf oplossingen die niet door draaien en spiegelen in elkaar kunnen worden overgevoerd heten uniek. De hieronder getoonde oplossingen zijn de twaalf unieke oplossingen. Elf van de twaalf unieke oplossingen hebben acht varianten, alleen de laatste unieke oplossing, die is puntsymmetrisch, heeft daardoor maar vier varianten. Ter controle: $8\times 11+4=92$ .

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h
	oplossing 1

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h
	oplossing 2

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h
	oplossing 3

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h
	oplossing 4

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h
	oplossing 5

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h
	oplossing 6

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h
	oplossing 7

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h
	oplossing 8

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h
	oplossing 9

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h
	oplossing 10

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h
	oplossing 11

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h
	oplossing 12

Aantal oplossingen

De onderstaande tabel geeft het aantal unieke^[11] en verschillende^[12] oplossingen voor het aantal $n$ koninginnen op een $n\times n$ bord.

n	Unieke oplossingen	Verschillende oplossingen
1	1	1
2, 3	0	0
4	1	2
5	2	10
6	1	4
7	6	40
8	12	92
9	46	352
10	92	724
11	341	2680
12	1787	14.200
13	9233	73.712
14	45.752	365.596
...
24	28.439.272.956.934	227.514.171.973.736
25	275.986.683.743.434	2.207.893,435.808.352
26	2.789.712.466.510.289	22.317.699.616.364.044

Vergelijkbare problemen

Hogere dimensies

Behalve dat het $n$ -damesprobleem het algemene geval is van het achtdamesprobleem, kan het probleem kan ook gesteld worden bij schaakruimtes van hogere dimensies. Zo kunnen bijvoorbeeld 4 dames geplaatst worden in een $3\times 3\times 3$ schaakruimte. Het is geweten dat in een schaakruimte van $d$ dimensies met grootte $n$ het niet altijd volstaat om $n$ dames te hebben.^[13]

Andere stukken

Vergelijkbare problemen kunnen geformuleerd worden met andere schaakstukken. Zo kunnen op een gewoon schaakbord 32 paarden, 14 lopers, 16 koningen of 8 torens geplaatst worden zonder dat ze elkaar slaan. Ook kunnen combinaties gemaakt worden van verschillende stukken, bijvoorbeeld het plaatsen van $n$ dames en $m$ paarden zonder dat de stukken elkaar kunnen aanvallen.^[14] In alle gevallen moet daarbij worden gelet op de toegestane zetten van de betreffende stukken in het schaakspel.

Schaakvariaties

Gelijkaardige problemen zijn te formuleren voor variaties op schaken, zoals shogi. Het $n+k$ -vliegendedraakprobleem bestaat er uit om $k$ shogipionnen en $n+k$ onderling niet aanvallende gepromoveerde torens te plaatsen op een $n\times n$ shogibord.^[15]

Aangepaste borden

Het is ook mogelijk om anders gevormde borden te gebruiken. Een voorbeeld is het torusvormige bord dat Pólya bestudeerde.^[16]

Dominantienummer

Het dominantienummer van een $n\times n$ schaakbord is het minimale aantal koninginnen dat op het bord moet staan zijn zodat elk vakje van het schaakbord bedekt is door een dame. Voor $n=8$ is dit 5.

Magische vierkant

In 1992 publiceerden Demirörs, Rafraf en Tanik een methode om bepaalde magische vierkanten om te zetten in oplossingen voor het $n$ -damesprobleem en omgekeerd.^[17]

Latijns vierkant

Het achtdamesprobleem kan voorgesteld worden als een Latijns vierkant.^[7]

Exacte overdekking

Het achtdamesprobleem kan herleid worden tot het probleem van het vinden van een exacte overdekking.^[18]

Vervolledigen van $n$ dames

Een gerelateerd probleem is het volgende: gegeven een $n\times n$ schaakbord waarop al enkele dames staan, is het dan mogelijk om een dame te plaatsen in elke resterende rij zodat geen enkele dame een andere dame kan aanvallen? In een paper van 2017 beweren de auteurs dat dit probleem NP-volledig is.^[19] Het is wel belangrijk om op te merken dat dit niet van toepassing is op het originele achtdamesprobleem; het feit dat er al dames op het bord staan is een cruciaal verschil.^[20]

Bronnen, noten en/of referenties

↑ (en) Hoffman, E. J., Loessi, J. C. en Moore, R. C. (maart 1969). Constructions for the Solution of the m Queens Problem. Mathematics Magazine 42 (2): 66-72 (Taylor & Francis). DOI: 10.2307/2689192. Gearchiveerd van origineel op 1 juli 2019. Geraadpleegd op 1 juli 2019.
↑ (en) Steinhaus, Hugo (1 januari 1999). Mathematical Snapshots. Courier Corporation, p. 29. ISBN 9780486409146. Gearchiveerd op 1 juli 2019.
↑ (en) Teresa W. Haynes, Stephen Hedetniemi, Peter Slater (5 januari 1998). Fundamentals of Domination in Graphs. CRC Press, p. 295. ISBN 9780824700331. Gearchiveerd op 12 juli 2019. Geraadpleegd op 1 juli 2019.
↑ (de) Nauck, Franz (1 juni 1850). Schach: Eine in das Gebiet der Mathematik fallende Aufgabe von Herrn Dr. Nauck in Schleusingen. Illustrirte Zeitung 14 (361).
↑ (en) Campbell, Paul J. (november 1977). Gauss and the eight queens problem: A study in miniature of the propagation of historical error. Historia Mathematica 4 (4): 397-404 (Elsevier). DOI: 10.1016/0315-0860(77)90076-3. Gearchiveerd van origineel op 11 april 2019. Geraadpleegd op 1 juli 2019.
↑ (en) Glaisher, J. W. (1874). On the problem of eight queens. Philosophical Magazine reeks 4 48: 457-467 (Taylor & Francis).
↑ ^a ^b (en) Bell, J., Brett, S. (6 januari 2009). A survey of known results and research areas for n-queens. Discrete Mathematics 309 (1): 1-31. Gearchiveerd van origineel op 1 juli 2019. Geraadpleegd op 1 juli 2019.
↑ (de) Pauls, E. (september 1874). Das Maximalproblem der Dame auf dem Schachbrete, II. Deutsche Schachzeitung 29 (9): 257-267 (Berliner Schachgesellschaft). Gearchiveerd van origineel op 1 juli 2019. Geraadpleegd op 1 juli 2019.
↑ Acht koninginnen puzzel
↑ E Dijkstra. A Short Introduction to the Art of Programming, augustus 1971. 9. The problem of eight queens
↑ rij A002562 in OEIS
↑ rij A000170 in OEIS
↑ (en) Barr, J., Rao, S. (2006). The n-Queens Problem in Higher Dimensions. Elemente der Mathematik 61 (4): 133-137. Gearchiveerd van origineel op 1 juli 2019.
↑ (en) Hui, Roger K. W. (mei 2005). Queens and Knights. Vector 21 (3): 78-88 (British APL Association). Geraadpleegd op 1 juli 2019.
↑ (en) Chatham, D. (31 december 2018). Reflections on the n +k dragon kings problem. Recreational Mathematics Magazine 5 (10): 39-55. DOI: 10.2478/rmm-2018-0007. Gearchiveerd van origineel op 1 juli 2019. Geraadpleegd op 1 juli 2019.
↑ (de) Pólya, G. (1984). Uber die "doppelt-periodischen" Losungen des n-Damen-Problems. George Pólya: Collected papers 4 (G-C): 237-247 (MIT Press).
↑ (en) Demirörs, O., Rafraf, N., Tanik, M. M. (1992). Obtaining n-queens solutions from magic squares and constructing magic squares from n-queens solutions. Journal of Recreational Mathematics 24: 272-280.
↑ (en) Knuth, DonaldKnuth, Donald (15 november 2000). Dancing links. Millenial Perspectives in Computer Science: 187-214. Gearchiveerd van origineel op 30 juni 2019. Geraadpleegd op 1 juli 2019.
↑ (en) Gent, Ian P., Jefferson, C., Nightingale, P. (30 augustus 2017). Complexity of n-Queens Completion. Journal of Artificial Intelligence Research 59: 815-848. ISSN: 1076-9757. DOI: 10.1613/jair.5512. Gearchiveerd van origineel op 1 juni 2019. Geraadpleegd op 1 juli 2019.
↑ (en) "The 8-Queens Puzzle", Clay Mathematics Institute, 2 september 2017. Gearchiveerd op 1 juli 2019. Geraadpleegd op 1 juli 2019.

[1] (en) Hoffman, E. J., Loessi, J. C. en Moore, R. C. (maart 1969). Constructions for the Solution of the m Queens Problem. Mathematics Magazine 42 (2): 66-72 (Taylor & Francis). DOI: 10.2307/2689192. Gearchiveerd van origineel op 1 juli 2019. Geraadpleegd op 1 juli 2019.

[2] (en) Steinhaus, Hugo (1 januari 1999). Mathematical Snapshots. Courier Corporation, p. 29. ISBN 9780486409146. Gearchiveerd op 1 juli 2019.

[3] (en) Teresa W. Haynes, Stephen Hedetniemi, Peter Slater (5 januari 1998). Fundamentals of Domination in Graphs. CRC Press, p. 295. ISBN 9780824700331. Gearchiveerd op 12 juli 2019. Geraadpleegd op 1 juli 2019.

[4] (de) Nauck, Franz (1 juni 1850). Schach: Eine in das Gebiet der Mathematik fallende Aufgabe von Herrn Dr. Nauck in Schleusingen. Illustrirte Zeitung 14 (361).

[5] (en) Campbell, Paul J. (november 1977). Gauss and the eight queens problem: A study in miniature of the propagation of historical error. Historia Mathematica 4 (4): 397-404 (Elsevier). DOI: 10.1016/0315-0860(77)90076-3. Gearchiveerd van origineel op 11 april 2019. Geraadpleegd op 1 juli 2019.

[6] (en) Glaisher, J. W. (1874). On the problem of eight queens. Philosophical Magazine reeks 4 48: 457-467 (Taylor & Francis).

[:0-7] (en) Bell, J., Brett, S. (6 januari 2009). A survey of known results and research areas for n-queens. Discrete Mathematics 309 (1): 1-31. Gearchiveerd van origineel op 1 juli 2019. Geraadpleegd op 1 juli 2019.

[8] (de) Pauls, E. (september 1874). Das Maximalproblem der Dame auf dem Schachbrete, II. Deutsche Schachzeitung 29 (9): 257-267 (Berliner Schachgesellschaft). Gearchiveerd van origineel op 1 juli 2019. Geraadpleegd op 1 juli 2019.

[9] Acht koninginnen puzzel

[10] E Dijkstra. A Short Introduction to the Art of Programming, augustus 1971. 9. The problem of eight queens

[11] rij A002562 in OEIS

[12] rij A000170 in OEIS

[13] (en) Barr, J., Rao, S. (2006). The n-Queens Problem in Higher Dimensions. Elemente der Mathematik 61 (4): 133-137. Gearchiveerd van origineel op 1 juli 2019.

[14] (en) Hui, Roger K. W. (mei 2005). Queens and Knights. Vector 21 (3): 78-88 (British APL Association). Geraadpleegd op 1 juli 2019.

[15] (en) Chatham, D. (31 december 2018). Reflections on the n +k dragon kings problem. Recreational Mathematics Magazine 5 (10): 39-55. DOI: 10.2478/rmm-2018-0007. Gearchiveerd van origineel op 1 juli 2019. Geraadpleegd op 1 juli 2019.

[16] (de) Pólya, G. (1984). Uber die "doppelt-periodischen" Losungen des n-Damen-Problems. George Pólya: Collected papers 4 (G-C): 237-247 (MIT Press).

[17] (en) Demirörs, O., Rafraf, N., Tanik, M. M. (1992). Obtaining n-queens solutions from magic squares and constructing magic squares from n-queens solutions. Journal of Recreational Mathematics 24: 272-280.

[18] (en) Knuth, DonaldKnuth, Donald (15 november 2000). Dancing links. Millenial Perspectives in Computer Science: 187-214. Gearchiveerd van origineel op 30 juni 2019. Geraadpleegd op 1 juli 2019.

[19] (en) Gent, Ian P., Jefferson, C., Nightingale, P. (30 augustus 2017). Complexity of n-Queens Completion. Journal of Artificial Intelligence Research 59: 815-848. ISSN: 1076-9757. DOI: 10.1613/jair.5512. Gearchiveerd van origineel op 1 juni 2019. Geraadpleegd op 1 juli 2019.

[20] (en) "The 8-Queens Puzzle", Clay Mathematics Institute, 2 september 2017. Gearchiveerd op 1 juli 2019. Geraadpleegd op 1 juli 2019.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]