Gegeven een getal n. Op hoeveel manieren kunnen nu n dames op een n bij n schaakbord staan zodanig dat geen dame een andere in één beurt kan slaan?Voor de volledigheid: een dame kan alle vakjes van de rij en de kolom waarin zij zich bevindt in één beurt bereiken; verder kan een dame zich ook schuin bewegen, dus alle vakjes in de twee diagonale richtingen kunnen ook direct bereikt worden. Het probleem is al bekend uit de vorige eeuw. Moeizaam werd het toen met de hand opgelost. Je moet in ieder geval een systematische methode bedenken, zodat je niks vergeet (en ook niks dubbel telt). Een voor de hand liggende methode is als volgt: zet een dame neer op één van de velden op de eerste rij van het bord. Die rij kan dan verder geen dames meer bevatten. Probeer nu alle velden van de tweede rij van een dame te voorzien zodanig dat deze geen ruzie heeft met de dame op de eerste rij. Als je zo'n plek gevonden hebt, ga je verder op de derde rij, enzovoorts. Om alle standen te vinden moet je er aan denken om alle mogelijkheden die er zijn volledig te onderzoeken: als je bijvoorbeeld de eerste dame gezet hebt, moet je alle mogelijke plekken op de tweede rij onderzoeken, en als je er daar weer tijdelijk één van gekozen hebt, ook alle plekken op de derde rij, enzovoorts. Hieronder staat de eerste oplossing die je zo vindt op het gewone 8 bij 8 bord.
| ** | |||||||
| ** | |||||||
| ** | |||||||
| ** | |||||||
| ** | |||||||
| ** | |||||||
| ** | |||||||
| ** |
Je kunt eenvoudig nagaan dat er geen oplossingen zijn als n kleiner is dan 4. Voor het 4 bij 4 bord zijn er 2 oplossingen, voor het 5 bij 5 bord 10, voor het 6 bij 6 bord 4, en voor het 8 bij 8 (gewone) bord 92. Dit laatste is al een stevige denkpartij. Overigens zijn er van deze 92 maar 12 essentieel verschillend.
Met een computer gaat dit allemaal wat beter. Je moet dan wel een programma
schrijven dat het probleem (bij gegeven n) oplost.
Dat gaan we nu proberen met behulp van de programmeertaal C++.
Dit is een taal die bijzonder geschikt is om
mee te leren programmeren. In Leiden wordt deze taal dan ook in het eerste jaar van
de studie bij het vak
Programmeermethoden
meteen goed geleerd. Je moet er een flink aantal kleine en grote
programma's in schrijven.
We nemen aan dat je kunt
omgaan met een UNIX-computer
(Linux is natuurlijk ook goed).
We bekijken het volgende stuk C++.
Zet dit als dam.cc ergens neer,
en compileer het met g++ -Wall -o dam dam.cc naar
een executeerbare file dam.
Zelfs alle mogelijke standen worden dan op het beeldscherm van de
computer afgedrukt.
Het programma is met name interessant
omdat er recursie in gebruikt wordt: dat is het principe dat een programma zichzelf
weer aanroept. Je ziet dat bij de functie zetdames, waarbinnen weer een keer
zetdames voorkomt. Het is hetzelfde idee dat ook wel het
Droste-effect genoemd wordt (denk maar aan de cacao-verpakking, waarop een verpleegster
weer een pakje cacao vasthoudt, waarop weer ...).
Voor meer informatie: zie hier. En er is veel over geschreven.
C++ is een zogenaamde "imperatieve" programmeertaal, wat betekent dat je de computer als het ware achter elkaar bevelen geeft: het programma. Er zijn ook andere programmeertalen, zoals de "functionele" programmeertaal Clean, en de "logische" programmeertaal PROLOG. In deze laatste kun je voor hetzelfde probleem een heel elegante oplossing opschrijven, waarbij je de computer min of meer alleen de eigenschappen van een correcte stand op het bord geeft. De computer, of liever PROLOG, zoekt dan zelf de manier om het probleem op te lossen. Ook deze talen komen volop aan de orde bij de studie Informatica aan de Universiteit Leiden!
Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.
11 november 2006 — http://www.liacs.nl/home/kosters/pm/dam.html