Heb je ooit schaak gespeeld? Zo ja, dan weet je dat de koningin het belangrijkste stuk is en dat zij een willekeurig aantal velden verticaal, horizontaal of diagonaal kan bewegen. Als dat niet zo is, hoeft u zich geen zorgen te maken: vandaag zullen we alleen leren hoe we 8 koninginnen op het schaakbord kunnen plaatsen, zodanig dat geen enkele koningin in staat is om naar een veld te gaan dat door een andere koningin wordt bezet. In schaakjargon zeggen we dan dat de koninginnen elkaar niet kunnen aanvallen. Hoe doen we dit? We gebruiken backtracking.
Het backtracking-algoritme vindt een oplossing voor problemen waarbij bepaalde beperkingen in acht moeten worden genomen. Het test alle mogelijke oplossingen totdat het de juiste vindt. Laten we een voorbeeld proberen, met vier koninginnen en een klein bord. We beginnen met het plaatsen van de eerste koningin:
The second step is to place the second queen in a safe position, and then the third one:
At this point, there is no safe square on which we can place the last queen. So, we will change the position of the previous one. This is backtracking!
As you can see, there is no other square to safely place the third queen, different than the one we tried. Hence, this will require multiple backtracks. We will have to go back again and change the position of the second queen we placed.
We will have to perform multiple backtracks again to place all queens correctly and finally obtain a solution:
If you want to learn more how multiple backtracking steps inevitably lead you to a solution, check out Computer Science Distilled. Het laat je ook veel andere computationele strategieën zien die je helpen om interessante problemen op te lossen!
Nu je weet hoe backtracking werkt, kunnen we het 8 koninginnen probleem op ware grootte oplossen. Hieronder staat een schaakbord waarmee je kunt spelen om je vaardigheden te oefenen en een oplossing te vinden. Begin met het plaatsen van de eerste koningin door op het linker bovenveld van het schaakbord te klikken. Je zult zien dat de koningin die je geplaatst hebt in de lijst “Huidige koninginnen” komt te staan.
Huidige koninginnen
Je kunt nu een andere koningin plaatsen op een positie die voorkomt dat ze elkaar aanvallen. Onze eerste koningin staat op a8, de tweede kan bijvoorbeeld op c7 worden geplaatst. Blijf koninginnen plaatsen tot er geen veilig veld op het schaakbord meer over is. Op dat moment is het tijd om terug te keren door op “ongedaan maken” te klikken. Hiermee wis je de laatst geplaatste koningin en kun je een ander veld kiezen om haar te plaatsen. U kunt ook een koningin van het bord verwijderen door er direct op te klikken.
Door het interactieve spel te spelen, kunt u een gevoel voor backtracking beginnen te krijgen. Als mens kan het moeilijk worden om alle vorige plaatsen van koninginnen bij te houden. Dit is waar programmeren helpt! Hieronder vind je een animatie van een programma dat zijn feilloze backtracking vaardigheden demonstreert:
Pseudocode:
- Start met het plaatsen van de eerste koningin op het linker bovenveld van het schaakbord.
- Als we de 8 koninginnen hebben geplaatst, zijn we klaar. Zo niet, is het dan mogelijk om nog een koningin op een veilige plaats te zetten?
- Zo ja, markeer dit dan als deel van de oplossing, en ga terug naar punt 2.
- Zo nee, verander dan de positie van de vorige koningin (backtracking) en ga terug naar punt 2.