Zebrapuzzel
De Zebrapuzzel is een bekende logische puzzel, die opgelost kan worden in de vorm van een logigram. Er bestaan veel versies van de puzzel, waaronder een die gepubliceerd was in de editie van Life International van 17 december 1962. In de editie van 25 maart 1963 stonden de oplossing en de namen van een paar honderd mensen van over de hele wereld die de puzzel opgelost hadden.
De puzzel wordt vaak Einsteins puzzel of Einsteins raadsel genoemd, omdat hij door Albert Einstein op jonge leeftijd zou zijn uitgevonden,[1] en soms wordt de puzzel aan Lewis Carroll toegeschreven.[2][3] Er is echter geen bewijs voor Einsteins of Carrolls auteurschap, en de versie in Life International bevat merknamen van sigaretten, zoals Kool, die nog niet tijdens Carrolls leven of Einsteins jeugd bestonden.
Er wordt vaak beweerd dat slechts 2% van de bevolking de puzzel kan oplossen.[4][5]
De Zebrapuzzel is gebruikt als een benchmark in de evaluatie van computeralgoritmes voor het oplossen van constraint satisfaction-problemen.[6]
Beschrijving
bewerkenDit is een vertaling van de versie van de puzzel die in 1962 in Life International verscheen:
- Er zijn vijf huizen.
- De Engelsman woont in het rode huis.
- De Spanjaard heeft een hond.
- De bewoner van het groene huis drinkt koffie.
- De Oekraïner drinkt thee.
- Het groene huis staat direct rechts van het witte huis.
- Degene die Old Gold rookt, houdt slakken als huisdieren.
- De bewoner van het gele huis rookt Kool.
- De bewoner van het middelste huis drinkt melk.
- De Noor woont in het eerste huis.
- Degene die Chesterfield rookt, woont naast degene die een vos heeft.
- Het huis waar Kool wordt gerookt, staat naast het huis met het paard.
- De Lucky Strike-roker drinkt sinaasappelsap.
- De Japanner rookt Parliament.
- De Noor woont naast het blauwe huis.
Welnu, wie drinkt er water? En wie heeft de zebra als huisdier?
Voor de duidelijkheid moet worden toegevoegd dat elk van de vijf huizen in een andere kleur geschilderd is, en dat hun bewoners van verschillende nationaliteiten zijn, verschillende huisdieren hebben, verschillende dranken drinken en verschillende Amerikaanse sigarettenmerken roken. Nog één ding: "rechts" in aanwijzing 6 betekent voor u rechts.
— Life International, 17 december 1962 (vertaling)
Oplossing
bewerkenErvan uitgaand dat één persoon water drinkt en één de eigenaar van de zebra is, is het niet alleen mogelijk om de twee vragen te beantwoorden, maar ook om de complete oplossing te achterhalen van wie waar woont, in welke kleur huis, welk huisdier heeft, welke drank drinkt en welk merk sigaretten rookt. Door aanwijzingen samen te evalueren is het mogelijk om stap voor stap conclusies te trekken die naar de unieke oplossing leiden. Aanwijzing 10 bijvoorbeeld stelt dat de Noor in het eerste huis woont, en uit aanwijzing 15 volgt dat het tweede huis blauw moet zijn. Het huis van de Noor kan dus niet blauw zijn, maar ook niet rood, waar de Engelsman woont (aanwijzing 2), noch groen of wit, want die staan naast elkaar (aanwijzing 6). Het huis moet dus geel zijn, wat tevens betekent dat de Noor sigaretten van het merk Kool rookt (aanwijzing 8).
Merk op dat aanwijzing 10 het "eerste" huis vermeldt, zonder duidelijk te maken of dat het huis uiterst links of uiterst rechts is als je ervoor staat. Het kiezen van een van beide kanten als het eerste huis heeft echter geen invloed op de antwoorden op de twee vragen, wie water drinkt en wie de zebra heeft.
Met behulp van het volgende logigramschema kan de puzzel opgelost worden. Als voorbeeld zijn de volgende stappen alvast in het logigram gezet:
- Volgens aanwijzing 2 moet de Engelsman in het rode huis wonen. Waar Engelsman en rood samenkomen zetten we een .
- De Engelsman woont dus niet in een ander kleur huis en de andere mensen wonen niet in het rode huis. Dus op de andere plaatsen in die rij en kolom zetten we een .
- Volgens aanwijzing 3 heeft de Spanjaard een hond. Net als bij aanwijzing 2 krijgen we zo één keer een en acht keer een .
- Nu kunnen we deze gegevens combineren: Omdat de hond het huisdier van de Spanjaard is en de Engelsman in het rode huis woont, woont de hond dus niet in het rode huis. Dit levert nog een op.
De oplossing is onderaan ingevuld (selecteer de tekst om deze zichtbaar te maken).
Andere versies
bewerkenAndere versies van de puzzel hebben diverse verschillen ten opzichte van die in Life International, zoals afwijkende kleuren, nationaliteiten, sigarettenmerken, drankjes en huisdieren, of de aanwijzingen in een andere volgorde. Deze veranderen de logica van de puzzel niet. Sommige versies van de puzzel hebben "Wie is eigenaar van de vis?" als afsluitende vraag.[7]
Sommige versies van de puzzel geven aan dat het groene huis links van het witte huis staat, in plaats van rechts.[4] De twee huizen, met al hun eigenschappen, wisselen hierdoor van plaats, wat de puzzel gemakkelijker op te lossen maakt.
Appendix
bewerkenDit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Zebra Puzzle op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.
Referenties
- ↑ Stangroom, Jeremy (2009). Einstein's Riddle: Riddles, Paradoxes, and Conundrums to Stretch Your Mind. Bloomsbury USA. ISBN 978-1-59691-665-4.
- ↑ M.R.C. van Dongen, How to Solve the Zebra Problem. Gearchiveerd op 19 augustus 2019. Geraadpleegd op 28 maart 2019.
- ↑ James Little, Capturing Constraint Programming Experience: A Case-Based Approach. Cork Constraint Computation Centre, University College, Cork, Ierland. Gearchiveerd op 2 februari 2021. Geraadpleegd op 28 maart 2019.
- ↑ a b Karttunen, Lauri, Einstein's Puzzle. Gearchiveerd op 11 januari 2020. Geraadpleegd op 28 maart 2019.
- ↑ Antonick, Gary, Numberplay: Einstein's Riddle. Blog in The New York Times (12 maart 2012). Gearchiveerd op 29 maart 2019. Geraadpleegd op 28 maart 2019.
- ↑ Prosser, Patrick (1993). Hybrid Algorithms for the Constraint Satisfaction Problem. Computational Intelligence 9 (3). Geraadpleegd op 28 maart 2019.
- ↑ Einstein's riddle, udel.edu. Geraadpleegd op 28 maart 2019.