Achtdamesprobleem

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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. Het achtdamesprobleem is een voorbeeld van het meer algemene -damesprobleem, waarbij dames op een schaakbord geplaatst moeten worden. Voor en kunnen er dames op het bord geplaatst worden, voor grotere kunnen dames geplaatst worden.[1][2]

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

In 1874 stelde de Engelse wiskundige James W. L. Glaisher voor om het achtdamesprobleem te veralgemenen naar dames.[6] Datzelfde jaar bewees Pauls dat de oplossing van Nauck volledig was: er bestaan niet meer dan 92 oplossingen.[7][8]

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 puntsymmetrisch is en daardoor maar 4 varianten heeft. Dat brengt het totaal op 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[9] en verschillende[10] oplossingen voor het aantal koninginnen op een 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]

Hogere dimensies[bewerken]

Zoals het probleem veralgemeend kan worden naar dames op een schaakbord, kan het probleem kan ook gesteld worden bij schaakruimtes van hogere dimensies. Zo kunnen bijvoorbeeld 4 dames geplaatst worden in een schaakruimte. Het is geweten dat in een schaakruimte van dimensies met grootte het niet altijd volstaat om dames te hebben.[11]

Andere stukken[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. Ook kunnen combinaties gemaakt worden van verschillende stukken, bijvoorbeeld het plaatsen van dames en paarden zonder dat de stukken elkaar kunnen aanvallen.[12]

Schaakvariaties[bewerken]

Gelijkaardige problemen zijn te formuleren voor variaties op schaken, zoals shogi. Het -vliegendedraakprobleem bestaat er uit om shogipionnen en onderling niet aanvallende gepromoveerde torens te plaatsen op een shogibord.[13]

Aangepaste borden[bewerken]

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

Dominantienummer[bewerken]

Het dominantienummer van een 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 is dit 5.

Magische vierkant[bewerken]

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

Latijns vierkant[bewerken]

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

Exacte overdekking[bewerken]

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

Vervolledigen van dames[bewerken]

Een gerelateerd probleem is het volgende: gegeven een 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.[17] 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.[18]