Einstein’s Riddle

Einstein Zebra C++ Prolog Constraint Programming

Einstein’s riddle was first presented to me in 2003. I had a great time solving it on paper. I then had an even better time digging up my Prolog skills to see if I still had that in me. Here’s the statement variant from Wikipedia:

  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

Want to give it a go before reading this? Despite the usual clickbaity claims that only such a low proportion of the world population can solve it, usually 2%, it’s not that hard. But it does need paper, pencil, and an eraser.

I won’t give away the answer in this post, so you can read anyway and come back to it later.1

Computer solving

Now, how would you solve this with a computer program? It’s easy to get distracted by details. The most easily reliable implementation is not to do it the same way you’d do it by hand. There’s too much bookkeeping to get it right on the first try, especially when there’s a much simpler approach. We can consider it a decision problem on the input space of all (nation, color, pet, drink, cigaratte) permutations: for each input, we’ll verify that all constraints apply. If they do, we can just scan for the water and the zebra.

There are 5! = 120 permutations of each property, so 5!5 = 24883200000 ≈ 2, 5 × 1010 permutations globally. It’s big. But it’s tractable. It’s actually a lot more tractable now than it was back in 2003.

Here’s a simple C++ program implementing that.2

#include <algorithm>
#include <array>
#include <iostream>
using namespace std;

enum nation_t { england, spain, ukraine, norway, japan };
enum color_t { red, green, ivory, yellow, blue };
enum pet_t { dog, snails, fox, horse, zebra };
enum drink_t { coffee, tea, milk, juice, water };
enum cigs_t {  old_gold, kool, chesterfield, lucky_strike, parliament };

template <typename T>
static bool next_to(array<T,5> attr, int i, T v)
  return (i <= 0 || attr[i-1] != v) && (i >= 4 || attr[i+1] != v);

template <typename A,typename B>
static bool both(int i, array<A,5>& ka, const A& va, array<B,5>& kb, const B& vb)
  return ka[i] == va && kb[i] != vb;

int main()
  array<nation_t, 5> nation;
  array<color_t,  5> color;
  array<pet_t,    5> pet;
  array<drink_t,  5> drink;
  array<cigs_t,   5> cigs;

  for (int i = 0; i < 5; i++)
    // This is horrible.  So I *LOVE* IT!!!
    // Try doing /that/ with std::iota!
    nation[i] = (nation_t) (
    color[i] = (color_t) (
    pet[i] = (pet_t) (
    drink[i] = (drink_t) (
    cigs[i] = (cigs_t) i))));

  for (;;) {
    int water_drinker, zebra_owner;

    // check the state against all constraints
    for (int i = 0; i < 5; i++) {
      if (both(i, nation, england, color, red))                 goto inconsistent;
      if (both(i, pet, dog, nation, spain))                     goto inconsistent;
      if (both(i, color, green, drink, coffee))                 goto inconsistent;
      if (both(i, nation, ukraine, drink, tea))                 goto inconsistent;
      if (color[i] == ivory && (i >= 4 || color[i+1] != green)) goto inconsistent;
      if (both(i, cigs, old_gold, pet, snails))                 goto inconsistent;
      if (both(i, cigs, kool, color, yellow))                   goto inconsistent;
      if (drink[i]  == milk && i != 2)                          goto inconsistent;
      if (i == 0 && nation[i] != norway)                        goto inconsistent;
      if (cigs[i] == chesterfield && next_to(pet,i,fox))        goto inconsistent;
      if (pet[i] == horse         && next_to(cigs,i,kool))      goto inconsistent;
      if (both(i, cigs, lucky_strike, drink, juice))            goto inconsistent;
      if (both(i, nation, japan, cigs, parliament))             goto inconsistent;
      if (nation[i] == norway     && next_to(color,i,blue))     goto inconsistent;

      if (drink[i] == water) water_drinker = nation[i];
      if (pet[i]   == zebra) zebra_owner   = nation[i];
    cout << "Found solution: " << water_drinker << ", " << zebra_owner << endl;
    /* fall through */

    // permute to next state
    if (!next_permutation(nation.begin(), nation.end()) &&
        !next_permutation(color.begin(), color.end())   &&
        !next_permutation(pet.begin(), pet.end())       &&
        !next_permutation(drink.begin(), drink.end())   &&
        !next_permutation(cigs.begin(), cigs.end()))
      goto lose; // no next state :-(
  return 0;

  cout << "No other solution found.\n";
  return 1;

Some noteworthy remarks about the translation from statement to code:

Let’s run it.

$ time ./brute
Found solution: 3, 4
No other solution found.

real	1m57,451s
user	1m57,299s
sys	0m0,028s

The solution is actually found closer to the beginning of that, approximately forty-five seconds in, but that’s distribution luck. And it is nice to check no other solution exists, and to get an idea of the time to exhaustively search the entire space.

Okay, so it’s solvable. That’s what I’ll call the brute-force approach.4 It’ll serve as an upper bound to what we’ll consider an acceptable solve time if we start doing better.

Beating brute force

Is doing better even possible? What part of the work can be removed? The insight will probably come easier with an example. The way the program is structured, we’re generating a permutation within the search space, and then checking it for all the constraints.

Consider constraint 10: “the Norwegian lives in the first house.” How discriminant is it? It’s not too hard to see the Norwegian guy will be generated in the first house in one one input out of five. When he isn’t, the input is globally invalid since it’s locally invalid, but a set of 4, 9 × 109 failing cases will be generated and evaluated anyway. That’s a huge waste! The common kind of constraint that pairs two attributes in a given house is even more discriminating.5

Generating only cases where the one-house attribute pairing constraints are valid is a bit of a pain in C++. But we can easily implement constraint 10. I’m not reproducing the code, but here’s the result.

$ time ./brute-10
Found solution: 0, 4
No other solution found.

real	0m26,434s
user	0m26,416s
sys	0m0,004s

(Don’t cringe at the figures being different. I wanted to keep the same simple initialization code, so I shuffled nations around to do it. It’s the same result all right.)

We can indeed observe it’s five times as fast.

How can we generalize short-circuiting to all of the constraints? Well, there’s no definitive generic easy way; it’s still an active area of research. A common rule of thumb is to start with the most discriminating ones, but that’s hindsight thinking.

Introducing backtracking

An easy step up from our brute-force will start with expressing the problem domain in a higher-level language. One where a partially assigned state can more easily be represented. I’ll use Prolog.6

The state will be a list of five house/5 functors. This is enough to represent the problem and unknowns. But it’s a little too much. We’re able to represent a state where each house has the same nationality, color, pet, drink and cigs. We can’t reasonably7 encode the extensive cross-house constraining: it’s what we’re solving for, it’s bound to be really unwieldy for a good reason. So we’ll have to remember to enforce that form of constraint explicitly.

Let’s define a few accessors, so as not to mix up the different attributes.

color (house(_,C,_,_,_),C).
pet   (house(_,_,P,_,_),P).
drink (house(_,_,_,D,_),D).
cigs  (house(_,_,_,_,C),C).

This time, the first constraint isn’t any different, and we can implement it directly on a Prolog list:

c1(S) :- length(S,5).

The “common” constraints all follow the same pattern: peek at the list members one by one, looking for a match that satisfies the rest of the clauses.

c2(S)  :- member(H,S), nation(H,england),    color(H,red).
c3(S)  :- member(H,S), nation(H,spain),      pet(H,dog).
c4(S)  :- member(H,S), drink(H,coffee),      color(H,green).
c5(S)  :- member(H,S), nation(H,ukraine),    drink(H,tea).
c7(S)  :- member(H,S), cigs(H,old_gold),     pet(H,snails).
c8(S)  :- member(H,S), cigs(H,kool),         color(H,yellow).
c13(S) :- member(H,S), cigs(H,lucky_strike), drink(H,orange_juice).
c14(S) :- member(H,S), nation(H,japan),      cigs(H,parliament).

Reading the first constraint c2 out loud for those who are a bit rusty in their Prolog: constraint 2 is verified for state S if there exists a house H in S, and the nation in H is England, and the color in H is red. “:-” reads as “if”; “,” reads as “and”.

Some constraints need access to the position in the list. Let’s start with the easy one, constraint 10, “the Norwegian lives in the first house.” We can pattern match8 on the state directly:

c10([H|_]) :- nation(H,norway).

Constraint 9 needs some notion of the “middle”. As I’m not hardcoding 5 this time, we’ll extract it from the list itself.

c9(S) :- length(S,L), M is L // 2, nth0(M,S,H), drink(H,milk).

Constraint 6 needs pairwise access to contiguous houses, to call a specific goal on each. We can do that by pattern matching on the list to check the base case, and recursing on the list’s tail for alternatives.

c6(S) :- seq(S,ap(color,ivory),ap(color,green)).

seq([L,R|_],ap(A,Va),ap(B,Vb)) :- call(A,L,Va), call(B,R,Vb).
seq([_|T],A,B) :- seq(T,A,B).

I’m using call/3 to keep it generic on the house attribute being tested, so I can re-use it for the “next to” class of constraints. I’ll implement those using a simple disjunction (boolean OR, represented with a semicolon “;” in Prolog) on the seq/3 basis.

next_to(S,A,B) :- seq(S,A,B) ; seq(S,B,A).

c11(S) :- next_to(S,ap(cigs,chesterfield),ap(pet,fox)).
c12(S) :- next_to(S,ap(cigs,kool),        ap(pet,horse)).
c15(S) :- next_to(S,ap(nation,norway),    ap(color,blue)).

All constraints are accounted for. We can now combine them.

puzzle(S) :- c1(S), c2(S), c3(S), c4(S), c5(S), c6(S), c7(S), 
  c8(S), c9(S), c10(S), c11(S), c12(S), c13(S), c14(S), c15(S).

And solve, instantly: (linebreaks mine)

?- puzzle(S).
S = [house(norway, yellow, fox, _1220, kool), 
     house(ukraine, blue, horse, tea, chesterfield),
     house(england, red, snails, milk, old_gold),
     house(spain, ivory, dog, orange_juice, lucky_strike),
     house(japan, green, _1182, coffee, parliament)] .

Don’t peek too deep if you still wanted to solve it on your own!

A few takeaway notes:

The kind of search we’re using here is a simple backtracking search. It applies each constraint in order, backtracking when one fails. If the entire chain succeeds, that’s a solution. The REPL then asks us whether we want to keep searching for other solutions. (There aren’t any.)

I implemented the constraints in statement order, and Prolog followed. But I’m not using any choice-guiding facility. So they could theoretically be ordered in any other way: we’d get the same result set. Having the “count” constraint first is a good heuristic. The predicates I used in this implementation are versatile enough to let Prolog find a solution in any order. Possibly in a much longer time.

State-of-the-art constraint programming engines can reorder constraints’ application in a number of ways to try and improve speed; we’re not going to do that.

What we are going to do is explore refining the variables a bit more. In the current state of the implementation, a variable can be in two states: assigned or unassigned. We’re leaving information on the table, right there. When we’re assigning the Norwegian to the first house, it should make it impossible to assign it again anywhere else. It ends up not changing the result, but a lot of futile possibilities are needlessly explored.

That ought to make the search better. But it’s already instantaneous. So we’ll have to look for a harder problem first. That’ll be the topic of another post.

In the meantime, enjoy this OR joke:

Constraint Programming is satisfying.

  1. And even if I did by accident, the fun in this kind of puzzle is in the solving process, not the solution. Kind of like Sudoku. But I find Sudoku boring, and implementing CSP solvers fun. YMMV.↩︎

  2. C++, on the other hand, wasn’t as good in 2003. std::array rocks!↩︎

  3. I know I’ve got anti-goto zealots in my followers. Most of them aren’t even coders. You are welcome to improve it on your own. I may even update it here. If it doesn’t make the code any more complex.↩︎

  4. I’m aware it’s possible to do worse without randomizing: by enumerating full 55 assignments per feature, for a grand total of 525 ≈ 3 × 1017 which is all the less tractable that it would need the additional checking we’re not duplicating a feature value. Ridiculous. Don’t do that. C++ supports permutations, use that.↩︎

  5. I count 2880, but I’ve been out of school for too long to be confident to state that in the article main text.↩︎

  6. I’m using SWI-Prolog, mostly because that’s what we used in school way back. I have no idea what the popular Prolog implementation is nowadays, but this one happens to still work.↩︎

  7. Must… resist… urge…↩︎

  8. Prolog calls it “unification”; it’s more general than pattern matching. But my readership is mostly Haskellers.↩︎