Het 8-koninginnenprobleem

In het item 'Over algoritmen' wordt iets gezegd over wat een algoritme is en vooral over wat het niet is.
Mijn eerste kennismaking met het begrip 'algoritme' dateert uit de tijd dat ik rondliep op de –toen nog‐ TH in Delft. Bij het vak 'Inleiding Informatica' (we leerden daar Algol60) werd dit algoritme uitgebreid besproken als voorbeeld van het voordeel van gestructureerd programmeren. Sindsdien heb ik dat met veel succes toegepast, maar is het voor mij ook een van de beste voorbeelden van theoretiseren voor het verkrijgen van kennis, maar verder van weinig praktisch nut. Dat terzijde.

Het 8-koninginnenprobleem is ook bekend als het achtdamesprobleem. Het is een schaakprobleem waarbij acht dames (koninginnen) 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.

Over het 8-koninginnenprobleem wordt op Wikipedia uitgebreid geschreven. Een (bewerkt) citaat:

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. 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". In 1874 bewees Pauls dat de oplossing van Nauck volledig was: er bestaan niet meer dan 92 oplossingen.

Met deze 92 oplossingen is iets merkwaardigs aan de hand: Als je de veldnamen (a1, …, a8, b1, …, b8, c1, … …, h8) in aanmerking neemt zijn er inderdaad 92 oplossingen. Als je de veldnamen niet in aanmerking neemt en alleen naar de plaats van de dames op het bord kijkt, blijkt er puntsymmetrie te bestaan. Er blijven dan maar 12 oplossingen over. In het volgende zal dat worden getoond.

Het algoritme
Het algorimte om het 8-koninginnenproblemen op te lossen wordt uitgelegd aan de hand van een 4×4-schaakbord, zie hiernaast. Dat is beter te behappen dan een 8×8 bord. We lossen dus een 4-koninginnenprobleem op.
Kolom voor kolom wordt geprobeerd om een dame te plaatsen. Als dat niet kan, of als de dame de overkant van het bord bereikt, wordt de dame in de vorige kolom één rij opgeschoven, waarna een nieuwe poging wordt gedaan.
Het algoritme stopt als de dame in de laatste kolom met succes is geplaatst.
Als het de dame in de eerste kolom de overkant bereikt stopt het algoritme. Er zijn geen of niet meer oplossingen.
In dit algoritme wordt elke nieuwe situatie na elke stap vergeleken met de vorige situatie. Aan de hand van de uitkomst van die test wordt besloten wat de volgende stap is. Dit heeft backtracking.
Het idee voor deze uitleg is ontleend aan de site van Pascal Huybers.

stap 1: Dame in kolom a. Deze komt op positie a1.
stap 2: Dame in kolom b. Deze komt op positie b3.
De "verboden" posities zijn met een rood dame-icoon aangeduid.
stap 3: Dame in kolom c. Er is geen enkele positie mogelijk.
stap 4: Dame in kolom b verschuift een rij (naar positie b4).
In kolom c komt de dame op positie c2.
stap 5: Dame in kolom d. Er is geen enkele positie mogelijk.
stap 6: Voor dame in kolom c zijn geen posities mogelijk. Ze bereikt de overkant.
stap 7: De dame in kolom b bereikt de overkant.
De dame in kolom a verschuift een rij en komt op positie a2.
stap 8: De dame in kolom b kan alleen op positie b4 staan.
stap 9: De dame in kolom c kan op positie c1 staan.
stap 10: De dame in kolom d kan op positie d3 staan.
stap 11: In kolom d (de laatste) is met succes een dame geplaatst. Er is een oplossing gevonden.
 
Het algoritme stopt.

Nu rijst de vraag of er nog meer oplossingen zijn. Om de vraag te beantwoorden starten we het algoritme opnieuw, waarbij we beginnen waar we geëindigd zijn toen we de (eerste) oplossing vonden.

stap 12: Dame in kolom d. Deze zou op positie d4 moeten komen, maar dat kan niet.
stap 13: De dame in kolom d heeft de overkant bereikt. De dame in kolom c moet een rij opschuiven, maar dat kan niet.
stap 14: De dame in kolom c heeft de overkant bereikt. De dame in kolom b moet een rij opschuiven, maar bereikt de overkant.
stap 15: De dame in kolom b heeft de overkant bereikt. De dame in kolom a schuift een rij op.
stap 16: De dame in kolom b komt op positie b1.
stap 17: De dame in kolom c komt op positie c4.
stap 18: De dame in kolom d komt op positie d2.
stap 19: In kolom d (de laatste) is met succes een dame geplaatst. Er is een oplossing gevonden.
 
Het algoritme stopt.

Nu rijst wederom de vraag of er nog meer oplossingen zijn. Om de vraag te beantwoorden starten we het algoritme weer opnieuw, waarbij we beginnen waar we geëindigd zijn toen we de tweede oplossing vonden.

stap 20: De dame in kolom d wordt opgeschoven, maar bereikt de overkant.
stap 21: De dame in kolom d heeft de overkant bereikt. De dame in kolom c moet een rij opschuiven, maar dat kan niet.
stap 22: De dame in kolom c heeft de overkant bereikt. De dame in kolom b moet een rij opschuiven, maar bereikt de overkant.
stap 23: De dame in kolom a schuift een rij op en komt op positie a4.
stap 24: De dame in kolom b komt op positie b1.
stap 25: De dame in kolom c komt op positie c3.
stap 26: In kolom d kan geen dame worden geplaatst.
stap 27: De dame in kolom c wordt opgeschoven, maar bereikt de overkant.
stap 28: De dame in kolom b wordt opgeschoven en komt op positie b2.
stap 29: In kolom c kan geen dame worden geplaatst.
stap 30: De dame in kolom b wordt opgeschoven, maar bereikt de overkant.
stap 31: De dame in kolom a wordt opgeschoven, maar bereikt de overkant.
Er zijn geen oplossingen (meer).
 
Het algoritme stopt. Er zijn dus in totaal twee oplossingen

De twee oplossingen vergeleken
Als je de plaatsing van de dames op het schaakbord van de twee oplossingen met elkaar vergelijkt, vallen een paar dingen op:

Op een 1×1-schaakbord kun je precies één dame kwijt. Dat is triviaal. Een 4×4-schaakbord is het kleinste bord waarop oplossingen met meerdere dames mogelijk zijn. Op de eerder genoemde Wikipedia-pagina vind je een lijst met aantallen mogelijke oplossingen. Daar staat ook een lijst met aantallen unieke oplossingen, dat wil zeggen: als er geen rekening wordt gehouden met kolom- en rijnummers.

Unieke oplossingen
Er wordt in het algoritme gebruik gemaakt van kolomnummers en rijnummers. Dat leidt er bij het 4×4-schaakbord toe dat er twee oplossingen zijn. Maar uit de symmetrie van de oplossingen is af te leiden dat beide oplossingen gelijkwaardig zijn. Als je niet let op kolom- en rijnummers, blijft er maar één unieke oplossing over.

Bij grotere borden treedt iets dergelijks op. Bij het 8×8-schaakbord blijven er van de 92 oplossingen er maar 12 over. Zie daarvoor ook de Wikipedia-pagina.

 
terug

html-682; Laatste wijziging: 30 september 2022