Achtdamesprobleem

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Het Achtdamesprobleem is een schaakprobleem waarbij acht dames zodanig op een schaakbord (van 8×8) 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.

Geschiedenis[bewerken]

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: 92. In 1872 bewees de Engelse wiskundige James Whitbread Lee Glaishe dat er niet meer oplossingen zijn. Daarmee was het oorspronkelijke probleem volledig opgelost.

Oplossingen[bewerken]

Het probleem kent 12 unieke oplossingen die hieronder zijn getoond. Door draaien en spiegelen heeft elke unieke oplossing 8 varianten, behalve de laatste unieke oplossing, die rotatiesymmetrisch is en daardoor maar 4 varianten heeft. Dat brengt het totaal op 8x11+4 = 92 oplossingen.

8 __ __ __ ql __ __ __ __
7 __ __ __ __ __ __ ql __
6 __ __ ql __ __ __ __ __
5 __ __ __ __ __ __ __ ql
4 __ ql __ __ __ __ __ __
3 __ __ __ __ ql __ __ __
2 ql __ __ __ __ __ __ __
1 __ __ __ __ __ ql __ __
a b c d e f g h
Unieke oplossing 1
8 __ __ __ __ ql __ __ __
7 __ ql __ __ __ __ __ __
6 __ __ __ ql __ __ __ __
5 __ __ __ __ __ __ ql __
4 __ __ ql __ __ __ __ __
3 __ __ __ __ __ __ __ ql
2 __ __ __ __ __ ql __ __
1 ql __ __ __ __ __ __ __
a b c d e f g h
Unieke oplossing 2
8 __ __ __ ql __ __ __ __
7 __ ql __ __ __ __ __ __
6 __ __ __ __ __ __ ql __
5 __ __ ql __ __ __ __ __
4 __ __ __ __ __ ql __ __
3 __ __ __ __ __ __ __ ql
2 __ __ __ __ ql __ __ __
1 ql __ __ __ __ __ __ __
a b c d e f g h
Unieke oplossing 3
8 __ __ __ ql __ __ __ __
7 __ __ __ __ __ ql __ __
6 __ __ __ __ __ __ __ ql
5 __ __ ql __ __ __ __ __
4 ql __ __ __ __ __ __ __
3 __ __ __ __ __ __ ql __
2 __ __ __ __ ql __ __ __
1 __ ql __ __ __ __ __ __
a b c d e f g h
Unieke oplossing 4
8 __ __ ql __ __ __ __ __
7 __ __ __ __ __ ql __ __
6 __ __ __ __ __ __ __ ql
5 ql __ __ __ __ __ __ __
4 __ __ __ ql __ __ __ __
3 __ __ __ __ __ __ ql __
2 __ __ __ __ ql __ __ __
1 __ ql __ __ __ __ __ __
a b c d e f g h
Unieke oplossing 5
8 __ __ __ __ ql __ __ __
7 __ __ ql __ __ __ __ __
6 __ __ __ __ __ __ __ ql
5 __ __ __ ql __ __ __ __
4 __ __ __ __ __ __ ql __
3 ql __ __ __ __ __ __ __
2 __ __ __ __ __ ql __ __
1 __ ql __ __ __ __ __ __
a b c d e f g h
Unieke oplossing 6
8 __ __ __ __ ql __ __ __
7 __ __ __ __ __ __ ql __
6 __ __ __ ql __ __ __ __
5 ql __ __ __ __ __ __ __
4 __ __ ql __ __ __ __ __
3 __ __ __ __ __ __ __ ql
2 __ __ __ __ __ ql __ __
1 __ ql __ __ __ __ __ __
a b c d e f g h
Unieke oplossing 7
8 __ __ __ ql __ __ __ __
7 ql __ __ __ __ __ __ __
6 __ __ __ __ ql __ __ __
5 __ __ __ __ __ __ __ ql
4 __ __ __ __ __ ql __ __
3 __ __ ql __ __ __ __ __
2 __ __ __ __ __ __ ql __
1 __ ql __ __ __ __ __ __
a b c d e f g h
Unieke oplossing 8
8 __ __ ql __ __ __ __ __
7 __ __ __ __ __ ql __ __
6 __ __ __ ql __ __ __ __
5 ql __ __ __ __ __ __ __
4 __ __ __ __ __ __ __ ql
3 __ __ __ __ ql __ __ __
2 __ __ __ __ __ __ ql __
1 __ ql __ __ __ __ __ __
a b c d e f g h
Unieke oplossing 9
8 __ __ __ __ __ ql __ __
7 __ ql __ __ __ __ __ __
6 __ __ __ __ __ __ ql __
5 ql __ __ __ __ __ __ __
4 __ __ __ ql __ __ __ __
3 __ __ __ __ __ __ __ ql
2 __ __ __ __ ql __ __ __
1 __ __ ql __ __ __ __ __
a b c d e f g h
Unieke oplossing 10
8 __ __ __ ql __ __ __ __
7 __ __ __ __ __ __ ql __
6 ql __ __ __ __ __ __ __
5 __ __ __ __ __ __ __ ql
4 __ __ __ __ ql __ __ __
3 __ ql __ __ __ __ __ __
2 __ __ __ __ __ ql __ __
1 __ __ ql __ __ __ __ __
a b c d e f g h
Unieke oplossing 11
8 __ __ __ __ __ ql __ __
7 __ __ __ ql __ __ __ __
6 __ __ __ __ __ __ ql __
5 ql __ __ __ __ __ __ __
4 __ __ __ __ __ __ __ ql
3 __ ql __ __ __ __ __ __
2 __ __ __ __ ql __ __ __
1 __ __ ql __ __ __ __ __
a b c d e f g h
Unieke oplossing 12

Aantal oplossingen[bewerken]

De onderstaande tabel geeft het aantal unieke[1] en verschillende[2] oplossingen voor het aantal (n) koninginnen op een n × 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[bewerken]

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.

Het is ook mogelijk om anders gevormde borden te gebruiken. Een voorbeeld is het torusvormige bord dat Polya bestudeerde.

Bronnen, noten en/of referenties
  1. rij A002562 in OEIS
  2. rij A000170 in OEIS