Puzzels oplossen

Op deze webpagina wordt uitgelegd hoe de volgende puzzels met behulp van een de computer kunnen worden opgelost:

1. Logiquiz puzzel
2. Sudoku puzzel
3. het '8 Koninginnen' probleem
4. boter, kaas een eieren

1. Logiquiz puzzel

De puzzel:

aan de hand van aanwijzigingen moet door middel van logisch nadenken worden beredeneerd hoe (wie-wat-waar-wanneer-hoeveel-...) een bepaalde activiteit heeft plaatsgevonden. Voor een voorbeeld: zie hier.

Benadering:

deze puzzel kan (automatisch) worden opgelost door alle mogelijke oplossingen op te sommen, en vervolgens voor ieder van de oplossingen te bekijken welke voldoet aan de aanwijzingen (als het goed is maar één (goede) oplossing).
Om alle mogelijke oplossingen te vinden, is het begrip permutatie belangrijk, wat aangeeft hoeveel mogelijke combinaties er bestaan.
Bijvoorbeeld: op hoeveel mogelijke manieren zijn drie gekleurde ballen (rood, groen, blauw) te verdelen over drie personen (eva, jan en pien) ?
dat zijn 3 x 2 x 1 = 6 verschillende manieren:

de permutatie wordt aangegeven met het uitroepteken (!) en is meestal wel te vinden op een standaard school rekenmachine: bv faculteit 3= 3! = 3 x 2 x 1 = 6
om het voorbeeld van de gekleurde ballen automatisch te kunnen verwerken wordt hier een getalnotatie gebruikt:


bovenstaande geldt voor één eigenschap ('kleur')
dit kan worden uitgebreid met een extra eigenschap (zie figuur hiernaast):
het aantal combinaties is nu 3! x 3! = 3 (kartesiaans produkt)

Programma afloop:

1. verzamelen alle permutaties van het probleem (permutations() )
hiermee kan, voor een permutatie, de waarde uit een kolom worden bepaald voor een persoon
 
2. verzamelen van alle inverse permutaties (invpermutations() )
hiermee kan het omgekeerde worden gedaan: gegeven een permutatie, bepalen van de persoon behorend bij een kolom/waarde
 
let op: de index voor 1. en 2. is gelijk, dwz betreffen dezelfde permutatie
 
3. verzamelen van alle mogelijke (combinaties) van permutaties (kartesiaans product) (allsolutions() )
 
4. invoeren van de opgave (thispuzzle() ) en (applylogic() )
 
5. toepassen van ieder van de logische aanwijzingen op de oplossingen (main() )
hiervoor kunnen twee functies gebruikt worden: wp() en pw(). Zie hieronder.
 
6. indien oplossing(en) zijn gevonden: afdrukken in leesbaar formaat (showuserfriendlysolution() )
 

Invoeren van een puzzel:

De aanwijzingen, zoals die bij de opgave van een puzzel gegeven worden, kunnen met twee functies ingevoerd worden. Deze twee functies zijn afdoende om alle voorkomende puzzels op te lossen:
 
pw(persoonnaam, kolomnaam):
voor de gegeven permutatie en de persoon, retourneert de waarde van de gegeven kolom
 
wp(kolomnaam, waardenaam):
voor de gegeven permutatie en de waarde uit de kolom, retourneert de persoon die daarbij hoort
 
Voorbeeld: voor de fictieve opgave 'reistijd' moet worden bepaald:
'wat is ieders reistijd, en hoe komt hij/zij op het werk ?'
 
aanwijzing: 'Mark reist iedere dag met de auto':
wp('vervoermiddel', 'auto') == 'mark'
 
aanwijzing: 'Daphne's reistijd verschilt met die van de wandelaar':
pw('daphne', 'reistijd') != pw(wp('vervoermiddel', 'benenwagen'), 'reistijd')
wp('vervoermiddel', 'benenwagen') != 'daphne'

Voorbeeld

Onderstaande puzzel is afkomstig van de website: logiquiz.nl
 
Opgave Gastsprekers © logiquiz.nl
 
Groep 8 ontvangt dit schooljaar enkele gastsprekers.
 
Aanwijzingen:
 
1. in december komt iemand, die geen tycho heet, over vuurwerk vertellen.
In mei spreekt een 45-jarige over vrijheid.
 
wp('maand', 'december') == wp('onderwerp', 'vuurwerk')
wp('onderwerp', 'vuurwerk') != 'tycho'
wp('maand', 'mei') == wp('onderwerp', 'vrijheid')
wp('onderwerp', 'vrijheid') == wp('leeftijd', '45')
 
2. Jeanet vertelt over nepwapens.
 
wp('onderwerp', 'nepwapens') == 'jeanet'
 
3. Degene die in februari over alcohol spreekt is 2 jaar jonger dan Peter.
 
wp('maand', 'februari') == wp('onderwerp', 'alcohol')
int(pw(wp('onderwerp', 'alcohol'), 'leeftijd')) + 2 == int(pw('peter', 'leeftijd'))
 
4. Tycho is 42 jaar oud. Cor is ouder dan Nina.
 
int(pw('tycho', 'leeftijd')) == 42
int(pw('cor', 'leeftijd')) > int(pw('nina', 'leeftijd'))
 
5. Wie in juni spreekt, heeft het niet over EHBO.
 
wp('maand', 'juni') != wp('onderwerp', 'ehbo')
 
Deze opgave is uitgewerkt in onderstaande python code:

De code

2. Sudoku puzzel

De puzzel:

De bedoeling van een sudoku puzzel is de 9x9 matrix (waarvan een aantal getallen al zijn gegeven) zodaning in te vullen met de getallen 1 t/m 9 dat in iedere rij, kolom of 3x3-kwadrant die getallen maar èèn keer voorkomen.

Benadering:

Aanvankelijk krijgt ieder vakje in de matrix alle mogelijke opties 1-9 toegewezen. Dan worden de reeds toegewezen (gevulde) vakjes gebruikt om de opties uit de aangrenzende vakjes weg te strepen. De resterende opties worden nu een voor een uitgeprobeerd, waarbij direkt de gekozen optie wordt doorgerekend in de aangrenzende vakjes. Soms (vaak) blijkt een ingeslagen weg niet te leiden tot een oplossing, waardoor moet worden terug gevallen naar een eerdere keuze. Dit wordt 'recursive backtracking' genoemd. Uiteindelijk resulteert dit in de (een) oplossing.

Programma afloop:

Alleereerst wordt (eenmalig) voor ieder vakje alle aangrenzende vakjes bepaald def calcpeers(), de zgn. 'peers'. Dan wordt voor ieder vakje de resterende opties bepaald: calcpuzzle() en cleanup(). Nu wordt voor iedere cel die nog opties over heeft, deze opties een voor een doorgerekend voor de resterende opties van andere cellen: isvalidcandidate() en cleanup(). De nog 'geldige' puzzels worden opgeslagen op de 'stack' waar ze ook weer vanaf kunnen worden gehaald (pop() , last-in-first-out).

Invoeren van een puzzel:

Zie onderstaand voorbeeld. De 'task' is een getallenreeks die van links naar rechts, van boven naar beneden, aangeeft welke vakjes reeds gevuld zijn. Er zijn een aantal voorbeelden gegeven.
Door te kiezen voor disclosure = True (of False) kan de uitvoer en snelheid worden bepaald.

Voorbeeld

Voor een specifieke opgave dienen alleen de task en disclosure te worden aangepast. Zie hieronder.

De code

3. het '8 koninginnen' probleem

De puzzel:

Hoe kunnnen acht koninginnen op een schaakbord worden geplaatst, zodanig dat geen van hen elkaar kan slaan ? Dit klassieke vraagstuk vraagt om een moderne benadering.

Benadering:

Door één stuk te plaatsen, worden de mogelijkheden om een tweede stuk te plaatsen beperkt (maar zijn er nog zeker), en een derde wordt nog verder beperkt. Door systematisch de mogelijkheden af te lopen, worden de oplossingen gevonden.

Programma afloop:

Ter voorbereiding wordt (eenmalig) voor ieder vakje alle aangrenzende vakjes bepaald (horizontaal, vertikaal, diagonaal) waarnaar een koniningin zich mag bewegen (validmoves()). Eerst wordt een koningin in het eerste vakje geplaats (linksboven), en bepaald wat nu de vrije posities zijn voor de rest van het speelbord. Dan wordt in de volgende kolom (kolom 2) gekeken of er nog een vrije positie is (freeposition()), zo ja dan wordt deze oplossing op de 'stack' geplaatst (queenspos.append()), zo niet dan wordt de vorige goede oplossing van de stack gehaald (queenspos.pop(), principe 'last in, first out'). Door dit te herhalen ('recursive backtracking') worden uiteindelijk alle oplossingen gevonden.

Invoeren van een puzzel:

Deze puzzel kent weinig varianten, behalve dan het formaat van het speelbord. Dit is in te stellen met de variable 'size'.

Voorbeeld

Het voorbeeld hieronder geeft alle oplossingen voor een speelbord met afmeting 8 (size = 8, een schaakbord).
De afmeting is zelf aan te passen, evenals de variable disclosure (True laat tussenstappen zien; False laat alleen het eindresultaat zien).

De code

4. boter, kaas en eieren

De puzzel:

Dit is het spelletje waarbij je om de beurt een rondje of een kruisje moet zetten, met als doel (als eerste) er drie op een rij te krijgen. In de film 'War Games' (1983) wordt beweerd dat het voor iedere speler mogelijk moet zijn in een 'remise' te eindigen, oftewel je hoeft nooit te verliezen (zie dit fragment).
Dit heb ik gepoogd in te bouwen in een spel, waarbij de speler (jij) het tegen de computer opneemt.

Benadering:

Om de computer minimaal een gelijk spel te laten behalen, zijn alle mogelijke spelvarianten opgesomd, met voor iedere spelsituatie de beste tegenzet. Daarbij wordt gebruik gemaakt van de symmetrie van het bord.
Bijvoorbeeld voor de eerste zet hoeven slechts drie spelsituaties beschreven te worden, te weten:

door te spiegelen of te draaien zijn alle andere varianten daarmee gedekt.
Op deze manier blijven er slechts 17 spelsituaties over waarmee de computer altijd een (winnende of 'niet-verliezende') tegenzet kan doen.

Programma afloop:

De code is geschreven in JavaScript/HTML5; grafisch wordt het CANVAS element gebruikt. De code is onderdeel van het HTML bestand en is dus op te vragen via de bron van de webpagina.
De functie onClick() wordt aangeroepen bij het click-event, en bekijkt waar de speler een zet wil plaatsen. Daarna is de computer aan de beurt, computermove(), waarbij wordt onderzocht of de ontstane spelsituatie via een transform() terug kan worden herleid naar een standaard spelsituatie sbg[]. Indien gevonden, dan wordt de bijbehorende standaard tegenzet scm[] terug getransformeerd naar de specifieke spelsituatie. Indien niet gevonden, dan maakt het niet (meer) uit waar de tegenzet wordt geplaatst.

Invoeren van een puzzel:

niet van toepassing. Klik waar je je zet wil plaatsen. Na ieder spel wisselen speler en computer wie er begint met de eerste zet.

Voorbeeld

niet van toepassing

De code

De code is ingebakken in de html file, en is als zodaning op te vragen (Explorer/Firefox/Chrome op Windows: Ctrl+U).