A Python solution to the Zebra Problem using logic programming
In 1962, Life International magazine published a logic puzzle that provided a series of clues about 5 houses that contain people and animals among other things, and asked the reader to figure out which house had the zebra in it:
- There are five houses.
- The Englishman lives in the red house.
- The Spaniard owns the dog.
- Coffee is drunk in the green house.
- The Ukrainian drinks tea.
- The green house is immediately to the right of the ivory house.
- The Old Gold smoker owns snails.
- Kools are smoked in the yellow house.
- Milk is drunk in the middle house.
- The Norwegian lives in the first house.
- The man who smokes Chesterfields lives in the house next to the man with the fox.
- Kools are smoked in the house next to the house where the horse is kept.
- The Lucky Strike smoker drinks orange juice.
- The Japanese smokes Parliaments.
- The Norwegian lives next to the blue house.
This problem can be solved programmatically in a number of ways. If you already know the technique to solving it (make a table), you can brute force it. However, it’s far more interesting and fun to solve the problem declaratively, using a logic solver.
So what? If it’s a big table, can’t you just dump it into a database and query it with SQL? The trouble is with these kinds of statements:
They drink water in a house next to the house where they smoke Blend.
Such a statement declares a relationship between some house and some other house. The word ‘some’ is actually very important here: it is a logic variable, which acts as a placeholder for a value without specifying a single actual value. It allows the solver to ‘try out’ different possible values and eventually (hopefully) land on a final one.
A logical solution
Here is such a solution using the logpy python library, which is an implementation of the miniKanren logic programming language:
This solution is adapted from / inspired by David Nolen’s solution using Clojure’s core.logic.
(See the full repo of my logpy examples, including an explanatory readme.)
What’s going on here?
If you’ve never done declarative programming, this can be kind of confusing. Think of each clue as a rule or constraint that specifies the way something must be. The solver’s job is to take all those constraints and tell you what (if any) values will satisfy all of them.
(eq, (var(), var(), var(), var(), var()), houses)
Sets up houses as a list of logic variables (each house), each of which will itself contain a list of logic variables (each property of that house), by saying “houses equals a list of 5 logic variables.” Note that this is actually declaring equality, not assignment.
(membero, ('Englishman', var(), var(), var(), 'red'), houses)
Stipulates that one of the houses has both the ‘Englishman’ and ‘red’ properties. The other properties are left ‘blank’ as logic variables, which get ‘filled in’ by the solver.
Once we’ve inputted all the rules, we run the solver by querying for
solutions = run(0, houses, zebraRules)
In other words, “What houses meet the requirements in zebraRules?” The answer may surprise you! 😉