Logigrammen, ken je die (nog)? Ik heb ze vroeger veel gedaan. Lekker strepen, kruizen en alles uit de hints persen, totdat de oplossing helemaal rond was.

Een van de bekendste logigrammen is de ‘Zebra puzzel’ of ook wel het ‘Raadsel van Einstein’ (niet dat Einstein hem heeft gemaakt, maar zo gaan die dingen).

Marty., ook bekend van “Zit een zebra in z’n flow? Laat hem zo!”

Het raadsel gaat als volgt:

Er zijn vijf huizen in vijf verschillende kleuren. In ieder huis woont iemand met een verschillende nationaliteit. De vijf personen drinken ieder iets verschillend, roken allemaal een ander type sigaar en hebben ieder een verschillend huisdier. Een iemand heeft een vis. De vraag is: wie?

Aanwijzingen:

  • De Brit woont in het rode huis.
  • De Zweed heeft honden als huisdier.
  • De Deen drinkt thee.
  • Het groene huis staat naast en links van het witte huis.
  • De eigenaar van het groene huis drinkt koffie.
  • De man die Pall Mall rookt houdt vogels.
  • De eigenaar van het gele huis rookt Dunhill.
  • De man die in het middelste huis woont drinkt melk.
  • De Noor woont in het eerste huis.
  • De man die Blends rookt woont naast degene die katten heeft.
  • De man die een paard heeft woont naast degene die Dunhill rookt.
  • De persoon die Blue Master rookt, drinkt bier.
  • De Duitser rookt Prince.
  • De Noor woont naast het blauwe huis.
  • De man die Blends rookt heeft een buurman die water drinkt.

Hartstikke leuk natuurlijk, zo’n raadsel, maar nog veel leuker om een programmaatje te schrijven dat dit raadsel zelf oplost.

Nu is deze puzzel prima brute force oplossen, net zoals bij tic-tac-toe. Daarbij loop je alle mogelijkheden door en check je telkens of de mogelijkheid klopt met de aanwijzingen. Er zijn 5 eigenschappen, per eigenschap 5 mogelijkheden, dus in totaal (5!)^5 = bijna 25 miljard mogelijkheden. Best veel, maar als je het slim aanpakt, prima te doen voor een computer.

Brute kracht

Maar dat is vrij dom en saai, want mogelijkheden aflopen ik al al vaker gedaan.

Dit keer leek het mij leuk een programmaatje te schrijven dat werkt zoals je zelf ook zo’n puzzel oplost: door één voor één de hints te vertalen naar (on)mogelijkheden en daaruit weer andere (on)mogelijkheden af te leiden.

Bij dit logigram hoort het volgende schema:

Laten we eens kijken naar de meest duidelijke hints:

  • De Brit woont in het rode huis.
  • De Zweed heeft honden als huisdier.
  • De Deen drinkt thee.
  • De eigenaar van het groene huis drinkt koffie.
  • De man die Pall Mall rookt houdt vogels.
  • De eigenaar van het gele huis rookt Dunhill.
  • De man die in het middelste huis woont drinkt melk.
  • De Noor woont in het eerste huis.
  • De persoon die Blue Master rookt, drinkt bier.
  • De Duitser rookt Prince.

Normaal zet je bij elk van de bovenstaande combinaties in het schema een kruisje, maar dat laat ik mijn programmaatje natuurlijk gewoon doen:

Voor een logigram geldt dat een eigenschap precies één keer moet worden toebedeeld. Dit betekent bijvoorbeeld dat, doordat de Noor op nummer 1 woont, de Noor dus niet een van de andere nummers kan wonen. Ook betekent het dat geen van de andere nationaliteiten op nummer 1 kan worden.

Dit geef je aan in het logigram door bijvoorbeeld een streepje te zetten. Ik leg deze logica vast in mijn programmaatje en zie hier het resultaat:

Er is nog meer informatie af te leiden uit deze hints. We zien dat de Noor niet in een rood huis woont, geen thee drinkt en geen Prince rookt en geen honden heeft. We weten ook dat de Noor op nummer 1 woont. We kunnen dus ook zeggen dat nummer 1 geen rood huis is, dat daar geen thee wordt gedronken, geen Prince wordt gerookt en geen honden zijn.

Ik voeg ook deze logica toe aan mijn programmaatje en dan is dit het resultaat:

Het zijn er dan misschien maar enkele streepjes meer, maar in dit soort puzzels is het vaak net dat ene streepje dat je weer verder helpt. Bovendien kan deze logica ons later vast weer verder helpen.

Voor nu er is alleen op basis van deze hints niets meer uit te persen. Tijd om naar de volgende groep hints te kijken:

  • De man die Blends rookt woont naast degene die katten heeft.
  • De man die een paard heeft woont naast degene die Dunhill rookt.
  • De Noor woont naast het blauwe huis.
  • De man die Blends rookt heeft een buurman die water drinkt.

In eerste instantie lijken we weinig aan deze buurmannen te hebben. Alleen de derde, De Noor woont in het blauwe huis levert direct wat op: De Noor woont op nummer 1, dus nummer twee moet wel het blauwe huis zijn.

Maar wie is wie?

Maar er is meer af te leiden. Als we de eerste bekijken, De man die Blends rookt woont naast degene die katten heeft, dan kunnen we hieruit afleiden dat de man die Blends rookt geen katten heeft, want die heeft zijn buurman. De man met een paard rookt dus ook geen Dunhill (hint 2) en de man die Blends rookt drinkt dus geen water (hint 4).

En er is nog meer: als we van een de positie weten, weten we van de ander ook meer (en andersom). Stel dat de ene op nummer 1 woont, moet de ander wel op nummer 2 wonen. Woont de een op nummer 5, dan moet de ander wel op nummer 4 wonen. Woont de een op nummer 2, 3, of 4, dan weten we waar de ander niet kan wonen, namelijk respectievelijk op 3 & 4, 1 & 5 en 1 & 2.

Als ik deze logica ook heb toegevoegd, verschijnen er weer een paar rode streepjes meer:

Tijd voor de laatste hint:

  • Het groene huis staat naast en links van het witte huis.

Deze hint lijkt op het eerste gezicht ook niet zo nuttig, want we weten nog niet waar het groene of witte huis staan.

Of deze

Maar schijn bedriegt, want er zijn zeker wel dingen af te leiden. Het groene huis kan bijvoorbeeld nooit op positie 5 staan en het witte huis nooit op nummer 1. Ook kunnen we zeggen dat als het witte huis ergens niet staat, het groene huis niet op de positie er links van kan staan (en omgekeerd).

Als ik ook deze logica heb toegevoegd aan het programmaatje is dit het resultaat:

Blijkbaar heeft het een tot het ander geleid, want de hele puzzel is opgelost!

Maar wie heeft de vis nu eigenlijk? Eén blik op het schema zegt genoeg:

Code beschikbaar op: https://github.com/gkruiger/logicpuzzle