Jump to content

Zebra Puzzle

From Wikipedia, the free encyclopedia

The Zebra Puzzle is a well-known logic puzzle. Many versions of the puzzle exist, including a version published in Life International magazine on December 17, 1962. The March 25, 1963, issue of Life contained the solution and the names of several hundred successful solvers from around the world.

The puzzle is often called Einstein's Puzzle or Einstein's Riddle because it is said to have been invented by Albert Einstein as a boy;[1] it is also sometimes attributed to Lewis Carroll.[2][3] However, there is no evidence for either person's authorship, and the Life International version of the puzzle mentions brands of cigarettes that did not exist during Carroll's lifetime or Einstein's boyhood.

The Zebra puzzle has been used as a benchmark in the evaluation of computer algorithms for solving constraint satisfaction problems.[4]

Description

[edit]

The following version of the puzzle appeared in Life International in 1962:

  1. There are five houses.
  2. The Englishman lives in the red house.
  3. The Spaniard owns the dog.
  4. Coffee is drunk in the green house.
  5. The Ukrainian drinks tea.
  6. The green house is immediately to the right of the ivory house.
  7. The Old Gold smoker owns snails.
  8. Kools are smoked in the yellow house.
  9. Milk is drunk in the middle house.
  10. The Norwegian lives in the first house.
  11. The man who smokes Chesterfields lives in the house next to the man with the fox.
  12. Kools are smoked in the house next to the house where the horse is kept.
  13. The Lucky Strike smoker drinks orange juice.
  14. The Japanese smokes Parliaments.
  15. The Norwegian lives next to the blue house.

Now, who drinks water? Who owns the zebra?

In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]. One other thing: in statement 6, right means your right.

— Life International, December 17, 1962[5]

Solution

[edit]

Assuming that one person drinks water and one owns a zebra, then it is possible not only to deduce the answers to the two questions, but to figure out a complete solution of who lives where, in what color house, keeping what pet, drinking what drink, and smoking what brand of cigarettes. By considering the clues a few at a time, it is possible to slowly build inferences that incrementally complete the puzzle's unique correct solution. For example, by clue 10, the Norwegian lives in house #1, and by clue 15, house #2 must be blue. The Norwegian's house therefore cannot be blue, nor can it be red, where the Englishman lives (clue 2), or green or ivory, which are next to each other (clue 6). It must therefore be yellow, which means the Norwegian also smokes Kools (clue 8).

The March 25, 1963, issue of Life International contained the following solution, and the names of several hundred solvers from around the world.

House 1 2 3 4 5
Color Yellow Blue Red Ivory Green
Nationality Norwegian Ukrainian Englishman Spaniard Japanese
Drink Water Tea Milk Orange juice Coffee
Smoke Kools Chesterfield Old Gold Lucky Strike Parliament
Pet Fox Horse Snails Dog Zebra

Other versions

[edit]

Other versions of the puzzle have various differences from the Life International puzzle, in which various colors, nationalities, cigarette brands, drinks, and pets are substituted,[6] or the clues are given in a different order. These do not change the logic of the puzzle.

A slightly simplified version of this puzzle appears in the video-game Dishonored 2, where the player character has to solve it to unlock a gate to an abandoned mansion.

Some versions of the puzzle indicate that the green house is on the left of the ivory house, instead of on the right of it.[7] This results in swapping the two corresponding houses with all their properties, and makes the puzzle easier to solve.[citation needed]

References

[edit]
  1. ^ Stangroom, Jeremy (2009). Einstein's Riddle: Riddles, Paradoxes, and Conundrums to Stretch Your Mind. Bloomsbury USA. pp. 10–11. ISBN 978-1-59691-665-4.
  2. ^ M.R.C. van Dongen. "How to Solve the Zebra Problem" (PDF). Retrieved November 6, 2013.
  3. ^ James Little; Cormac Gebruers; Derek Bridge & Eugene Freuder. "Capturing Constraint Programming Experience: A Case-Based Approach" (PDF). Cork Constraint Computation Centre, University College, Cork, Ireland. Retrieved September 5, 2009.
  4. ^ Prosser, Patrick (1993). "Hybrid Algorithms for the Constraint Satisfaction Problem" (PDF). Computational Intelligence. 9 (3): 268–299. doi:10.1111/j.1467-8640.1993.tb00310.x. S2CID 36951414.
  5. ^ Vassberg, Dylan; Vassberg, J. (November 20, 2009). Is Einstein's Puzzle Over-Specified?. 21st Century Challenges in Computational Engineering & Science. ResearchGate. Princeton, NJ. Retrieved July 8, 2021. Includes a scan of the original Life puzzle.{{cite conference}}: CS1 maint: postscript (link)
  6. ^ "Who Owns The Fish? Solution". math.ucsd.edu. Archived from the original on June 30, 2010.
  7. ^ Karttunen, Lauri. "Einstein's Puzzle". Retrieved November 1, 2014.
[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Zebra_Puzzle&oldid=1183109914"