Informatica

hersenkrakers oplossen met de computer


Inleiding

Hoe zet je acht koninginnen op een schaakbord zodat ze elkaar niet kunnen slaan? Of hoe zorg je ervoor dat je maar één pion overhoudt op het solitaire bord? Heb je altijd al het antwoord willen weten op zulk soort puzzels, maar heb je nooit zin om er over na te denken, dan is er maar één oplossing: Laat de computer het voor je doen.

Graaftransformaties

Een handige techniek bij het oplossen van dergelijke problemen is het gebruik van graaftransformaties. Deze techniek biedt een gestructureerde analyse en oplossing voor problemen. Een graaf in de wiskunde is een verzameling knopen. Knopen kunnen een of meer labels hebben. Tussen de knopen lopen pijlen, pijlen hebben altijd maar 1 label. Een voorbeeld van een graaf is bijvoorbeeld een afbeelding van het spoorwegennet. Een graaftransformatie is niets anders dan de aanpassing van een graaf naar een nieuwe graaf. Dit kan door het toevoegen van nieuwe knopen aan de graaf of door het verplaatsen van pijlen. Dit is allemaal nog behoorlijk abstract, dus laten we een klein voorbeeld geven. In een vijver liggen 5 stenen met op de linker twee stenen twee groene kikkers en op de rechter twee stenen twee rode kikkers. De groene kikkers moeten naar rechts en de rode naar links, de volgende regels moeten hierbij in acht genomen worden. Een groene kikkers mag een stap naar rechts doen als de steen rechts van hem vrij is, ook mag hij over één kikker heen springen als de steen waar hij op terecht komt ook leeg is. Dezelfde regels gelden ook voor de rode kikkers, maar dan in tegengestelde richting. In deze situatie hebben we negen knopen nodig voor de 5 stenen plus vier kikkers. Om aan te geven hoe de stenen t.o.v. elkaar liggen tekenen we "links en rechts" pijlen tussen de stenen en tenslotte tekenen we een aantal "zit op" pijlen tussen de kikkers en de stenen om aan te geven op welke stenen kikkers zitten. De transformaties die bij dit probleem horen, zijn alle geldige zetten. Een transformatie wordt dus ook beschreven in regels, waarbij elke regel slechts één transformatie beschrijft. Voordat een regel toegepast kan worden moet het echter wel voldoen aan een patroon. In het geval van de kikkers betekent dit bijvoorbeeld dat een steen leeg moet zijn als een kikker daarop wil springen.

Bij het maken van je PWS kun je kiezen uit verschillende interessante puzzels. Enkele voorbeelden staan in de bijlage, samen met een uitgebreidere uitleg van graaftransformaties. Verder wordt er ook aangegeven waar je de software kunt downloaden die nodig is voor de graaftransformaties.

onderzoeksvragen