Solving “Who owns the Zebra” programmatically?

Question

Edit: this puzzle is also known as "Einstein's Riddle"

The Who owns the Zebra (you can try the online version here) is an example of a classic set of puzzles and I bet that most people on Stack Overflow can solve it with pen and paper. But what would a programmatic solution look like?

Based on the clues listed below...

• There are five houses.
• Each house has its own unique color.
• All house owners are of different nationalities.
• They all have different pets.
• They all drink different drinks.
• They all smoke different cigarettes.
• The English man lives in the red house.
• The Swede has a dog.
• The Dane drinks tea.
• The green house is on the left side of the white house.
• They drink coffee in the green house.
• The man who smokes Pall Mall has birds.
• In the yellow house they smoke Dunhill.
• In the middle house they drink milk.
• The Norwegian lives in the first house.
• The man who smokes Blend lives in the house next to the house with cats.
• In the house next to the house where they have a horse, they smoke Dunhill.
• The man who smokes Blue Master drinks beer.
• The German smokes Prince.
• The Norwegian lives next to the blue house.
• They drink water in the house next to the house where they smoke Blend.

...who owns the Zebra?

Answer 1

Here is an excerpt from the full solution using NSolver, posted at Einstein’s Riddle in C#:

// The green house's owner drinks coffee
Post(greenHouse.Eq(coffee));
// The person who smokes Pall Mall rears birds 
Post(pallMall.Eq(birds));
// The owner of the yellow house smokes Dunhill 
Post(yellowHouse.Eq(dunhill));

Answer 2

This is really a constraint solving problem. You can do it with a generalized kind of constraint propagation in logic-programming like languages. We have a demo specifically for the Zebra problem in the ALE (attribute logic engine) system:

http://www.cs.toronto.edu/~gpenn/ale.html

Here's the link to the coding of a simplified Zebra puzzle:

http://www.cs.toronto.edu/~gpenn/ale/files/grammars/baby.pl

To do this efficiently is another matter.

Answer 3

SWI-Prolog compatible:

% NOTE - This may or may not be more efficent. A bit verbose, though.
left_side(L, R, [L, R, _, _, _]).
left_side(L, R, [_, L, R, _, _]).
left_side(L, R, [_, _, L, R, _]).
left_side(L, R, [_, _, _, L, R]).

next_to(X, Y, Street) :- left_side(X, Y, Street).
next_to(X, Y, Street) :- left_side(Y, X, Street).

m(X, Y) :- member(X, Y).

get_zebra(Street, Who) :- 
    Street = [[C1, N1, P1, D1, S1],
              [C2, N2, P2, D2, S2],
              [C3, N3, P3, D3, S3],
              [C4, N4, P4, D4, S4],
              [C5, N5, P5, D5, S5]],
    m([red, english, _, _, _], Street),
    m([_, swede, dog, _, _], Street),
    m([_, dane, _, tea, _], Street),
    left_side([green, _, _, _, _], [white, _, _, _, _], Street),
    m([green, _, _, coffee, _], Street),
    m([_, _, birds, _, pallmall], Street),
    m([yellow, _, _, _, dunhill], Street),
    D3 = milk,
    N1 = norwegian,
    next_to([_, _, _, _, blend], [_, _, cats, _, _], Street),
    next_to([_, _, horse, _, _], [_, _, _, _, dunhill], Street),
    m([_, _, _, beer, bluemaster], Street),
    m([_, german, _, _, prince], Street),
    next_to([_, norwegian, _, _, _], [blue, _, _, _, _], Street),
    next_to([_, _, _, water, _], [_, _, _, _, blend], Street),
    m([_, Who, zebra, _, _], Street).

At the interpreter:

?- get_zebra(Street, Who).
Street = ...
Who = german

Answer 4

ES6 (Javascript) solution

With lots of ES6 generators and a little bit of lodash. You will need Babel to run this.

var _ = require('lodash');

function canBe(house, criteria) {
    for (const key of Object.keys(criteria))
        if (house[key] && house[key] !== criteria[key])
            return false;
    return true;
}

function* thereShouldBe(criteria, street) {
    for (const i of _.range(street.length))
        yield* thereShouldBeAtIndex(criteria, i, street);
}

function* thereShouldBeAtIndex(criteria, index, street) {
    if (canBe(street[index], criteria)) {
        const newStreet = _.cloneDeep(street);
        newStreet[index] = _.assign({}, street[index], criteria);
        yield newStreet;
    }
}

function* leftOf(critA, critB, street) {
    for (const i of _.range(street.length - 1)) {
        if (canBe(street[i], critA) && canBe(street[i+1], critB)) {
            const newStreet = _.cloneDeep(street);
            newStreet[i  ] = _.assign({}, street[i  ], critA);
            newStreet[i+1] = _.assign({}, street[i+1], critB);
            yield newStreet;
        }
    }
}
function* nextTo(critA, critB, street) {
    yield* leftOf(critA, critB, street);
    yield* leftOf(critB, critA, street);
}

const street = [{}, {}, {}, {}, {}]; // five houses

// Btw: it turns out we don't need uniqueness constraint.

const constraints = [
    s => thereShouldBe({nation: 'English', color: 'red'}, s),
    s => thereShouldBe({nation: 'Swede', animal: 'dog'}, s),
    s => thereShouldBe({nation: 'Dane', drink: 'tea'}, s),
    s => leftOf({color: 'green'}, {color: 'white'}, s),
    s => thereShouldBe({drink: 'coffee', color: 'green'}, s),
    s => thereShouldBe({cigarettes: 'PallMall', animal: 'birds'}, s),
    s => thereShouldBe({color: 'yellow', cigarettes: 'Dunhill'}, s),
    s => thereShouldBeAtIndex({drink: 'milk'}, 2, s),
    s => thereShouldBeAtIndex({nation: 'Norwegian'}, 0, s),
    s => nextTo({cigarettes: 'Blend'}, {animal: 'cats'}, s),
    s => nextTo({animal: 'horse'}, {cigarettes: 'Dunhill'}, s),
    s => thereShouldBe({cigarettes: 'BlueMaster', drink: 'beer'}, s),
    s => thereShouldBe({nation: 'German', cigarettes: 'Prince'}, s),
    s => nextTo({nation: 'Norwegian'}, {color: 'blue'}, s),
    s => nextTo({drink: 'water'}, {cigarettes: 'Blend'}, s),

    s => thereShouldBe({animal: 'zebra'}, s), // should be somewhere
];

function* findSolution(remainingConstraints, street) {
    if (remainingConstraints.length === 0)
        yield street;
    else
        for (const newStreet of _.head(remainingConstraints)(street))
            yield* findSolution(_.tail(remainingConstraints), newStreet);
}

for (const streetSolution of findSolution(constraints, street)) {
    console.log(streetSolution);
}

Result:

[ { color: 'yellow',
    cigarettes: 'Dunhill',
    nation: 'Norwegian',
    animal: 'cats',
    drink: 'water' },
  { nation: 'Dane',
    drink: 'tea',
    cigarettes: 'Blend',
    animal: 'horse',
    color: 'blue' },
  { nation: 'English',
    color: 'red',
    cigarettes: 'PallMall',
    animal: 'birds',
    drink: 'milk' },
  { color: 'green',
    drink: 'coffee',
    nation: 'German',
    cigarettes: 'Prince',
    animal: 'zebra' },
  { nation: 'Swede',
    animal: 'dog',
    color: 'white',
    cigarettes: 'BlueMaster',
    drink: 'beer' } ]

Run time is around 2.5s for me, but this can be improved a lot by changing the order of rules. I decided to keep the original order for clarity.

Thanks, this was a cool challenge!

Answer 5

In PAIP (Chapter 11), Norvig solves the zebra puzzle using a Prolog embedded in Lisp.

Answer 6

The easiest way to solve such problems programmatically is to use nested loops over all permutations and check to see if the result satisfies the predicates in the question. Many of the predicates can be hoisted from the inner loop to outer loops in order to dramatically reduce the computational complexity until the answer can be computed in a reasonable time.

Here is a simple F# solution derived from an article in the F# Journal:

let rec distribute y xs =
  match xs with
  | [] -> [[y]]
  | x::xs -> (y::x::xs)::[for xs in distribute y xs -> x::xs]

let rec permute xs =
  match xs with
  | [] | [_] as xs -> [xs]
  | x::xs -> List.collect (distribute x) (permute xs)

let find xs x = List.findIndex ((=) x) xs + 1

let eq xs x ys y = find xs x = find ys y

let nextTo xs x ys y = abs(find xs x - find ys y) = 1

let nations = ["British"; "Swedish"; "Danish"; "Norwegian"; "German"]

let houses = ["Red"; "Green"; "Blue"; "White"; "Yellow"]

let drinks = ["Milk"; "Coffee"; "Water"; "Beer"; "Tea"]

let smokes = ["Blend"; "Prince"; "Blue Master"; "Dunhill"; "Pall Mall"]

let pets = ["Dog"; "Cat"; "Zebra"; "Horse"; "Bird"]

[ for nations in permute nations do
    if find nations "Norwegian" = 1 then
      for houses in permute houses do
        if eq nations "British" houses "Red" &&
           find houses "Green" = find houses "White"-1 &&
           nextTo nations "Norwegian" houses "Blue" then
          for drinks in permute drinks do
            if eq nations "Danish" drinks "Tea" &&
               eq houses "Green" drinks "Coffee" &&
               3 = find drinks "Milk" then
              for smokes in permute smokes do
                if eq houses "Yellow" smokes "Dunhill" &&
                   eq smokes "Blue Master" drinks "Beer" &&
                   eq nations "German" smokes "Prince" &&
                   nextTo smokes "Blend" drinks "Water" then
                  for pets in permute pets do
                    if eq nations "Swedish" pets "Dog" &&
                       eq smokes "Pall Mall" pets "Bird" &&
                       nextTo pets "Cat" smokes "Blend" &&
                       nextTo pets "Horse" smokes "Dunhill" then
                      yield nations, houses, drinks, smokes, pets ]

The output obtained in 9ms is:

val it :
  (string list * string list * string list * string list * string list) list =
  [(["Norwegian"; "Danish"; "British"; "German"; "Swedish"],
    ["Yellow"; "Blue"; "Red"; "Green"; "White"],
    ["Water"; "Tea"; "Milk"; "Coffee"; "Beer"],
    ["Dunhill"; "Blend"; "Pall Mall"; "Prince"; "Blue Master"],
    ["Cat"; "Horse"; "Bird"; "Zebra"; "Dog"])]