Het achtkoninginnenprobleem
Het achtkoninginnenprobleem vraagt om acht dames op een schaakbord waarvan er geen twee elkaar aanvallen. De schaakcomponist Max Bezzel publiceerde het in 1848, en het is het klassieke eerste voorbeeld van zoeken met backtracking geworden.
Een schaakpuzzel uit 1848
Max Bezzel, een Duitse schaakcomponist, legde de puzzel in 1848 voor in een Berlijns schaaktijdschrift. Franz Nauck publiceerde in 1850 alle 92 oplossingen en stelde dezelfde vraag voor grotere borden. Carl Friedrich Gauss volgde de puzzel met belangstelling en besprak hem in zijn brieven.
Eén dame per rij en kolom
Acht dames die elkaar niet aanvallen, moeten in acht verschillende rijen en acht verschillende kolommen staan. Een oplossing is dus een herschikking van de getallen 1 tot en met 8, een permutatie, met één extra regel: geen twee dames mogen dezelfde diagonaal delen. Van de 40.320 permutaties komen er maar 92 door.
Backtracking
Backtracking bouwt een oplossing stukje voor stukje op en gaat terug zodra het op een doodlopend spoor stuit. Voor de dames: zet een dame op het eerste veilige veld van de volgende rij, en als een rij geen veilig veld heeft, ga dan terug naar de rij erboven en schuif die dame door. In 1972 gebruikte Edsger Dijkstra de puzzel om met precies deze zoektocht gestructureerd programmeren uit te leggen.
Symmetrie
Draai het bord een kwartslag, of spiegel het, en een oplossing blijft een oplossing. Dat geeft tot acht versies van elke oplossing. De 92 oplossingen vallen uiteen in 12 van zulke families: elf met 8 leden, en één met maar 4, omdat die oplossing er na een halve draai hetzelfde uitziet.
Het n-koninginnenprobleem
Op een n×n-bord is de vraag dezelfde, met n dames. Er zijn oplossingen voor elke n vanaf 4, en hun aantal groeit snel: 2 bij 4×4, 92 bij 8×8 en 14.200 bij 12×12. Er is geen formule voor het aantal bekend; de recordwaarden komen uit grote computerzoektochten.
Probeer het in PictorX
Open Acht dames en klik op een veld om een dame te plaatsen; klik er nog eens op om haar weer weg te halen. ‘Aanvallen tonen’ zet een stip op de velden die je dames aanvallen, en rode dames vallen elkaar aan. Oplossen voert de zoektocht met backtracking stap voor stap uit en laat de dames die je hebt geplaatst staan. Volgende oplossing loopt alle oplossingen op volgorde door, en Grootte verandert het bord van 4×4 tot 12×12.
Veelgestelde vragen
Wie heeft het achtkoninginnenprobleem bedacht?
Max Bezzel, een Duitse schaakcomponist, in 1848. Franz Nauck publiceerde in 1850 de eerste volledige lijst met oplossingen.
Hoeveel oplossingen zijn er?
92 op het standaardbord. Als je draaiingen en spiegelingen als één telt, zijn het er 12.
Waarom heeft het 6×6-bord zo weinig oplossingen?
Het heeft er maar 4, allemaal uit één familie. Het kleinere 5×5-bord heeft er 10. Grotere borden hebben er steeds meer: 40 op 7×7 en 92 op 8×8.
Uploadt PictorX iets?
Nee. Het bord wordt op een canvas in je browser getekend. Opslaan downloadt een PNG, en Bewerken opent dat beeld in de PictorX-editor.
Gerelateerde gereedschappen
Acht dames
Plaats acht dames zo op een schaakbord dat geen enkele een andere aanvalt. Probeer het zelf, kijk hoe de zoektocht met backtracking stap voor stap een oplossing vindt, en loop alle 92 oplossingen door.
Paardensprong
Laat een schaakpaard precies één keer op elk veld van het bord springen. Speel zelf met de hints van Warnsdorff, of kijk hoe Oplossen een open of gesloten rondgang afmaakt. Sla de route op als PNG.
De paardensprong
De geschiedenis en wiskunde van de paardensprong: Euler en Warnsdorff, open en gesloten rondgangen, waarom borden met oneven afmetingen geen gesloten rondgang hebben en hoe een computer er een vindt.
Torens van Hanoi
Verplaats in je browser een toren van schijven over drie pinnen. Eén schijf tegelijk, nooit een grotere op een kleinere. De kortste oplossing is 2ⁿ − 1 zetten.
Torens van Hanoi
De Torens van Hanoi: drie pinnen, één schijf tegelijk en nooit een grotere op een kleinere. De kortste oplossing is 2ⁿ−1 zetten. Édouard Lucas bracht de puzzel in 1883 uit.
Langtons Mier
Draai Langtons mier in je browser. Bekijk symmetrie, chaos en de snelweg van 104 stappen, en probeer daarna meerkleurige regels, meerdere mieren, een zeshoekig raster en turmites.
Klaar om het te proberen?
Open PictorX in uw browser - geen installatie, geen creditcard vereist om te starten.
Probeer Acht dames