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.¹

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!⁵ = 24883200000 ≈ 2, 5 × 10¹⁰ 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.²

#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 */
  inconsistent:

    // 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;

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

Some noteworthy remarks about the translation from statement to code:

• The first constraint is of a different nature. It has implications not only on the number of slots to allocate, but also on the number of elements in the enumerations. That’s why I’m not making it a variable or even a constant. The code works for five, and only five.
• The property sets were constructed by scanning the constraints and queries.
• The both() helper implements a failure check for proposition “if this house index verifies property A, then it must also validate property B”. This explains both why the check is == on A and != on B, and why A and B are sometimes in a different order than they appeared in the initial text.
• Yes, I’m using goto. This kind of constraint satisfaction where the goal is reached after succeeding at a sieve of tests is very conducive to short-circuiting in this manner.³

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.⁴ 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 × 10⁹ 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.⁵

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.⁶

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 reasonably⁷ 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.

nation(house(N,_,_,_,_),N).
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 match⁸ 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:

• I did not encode the actual puzzle queries this time. So there’s no “water” or “zebras” in the results: we get anonymous free variables instead.
• Remember how I said the data structure wouldn’t take care of ensuring we didn’t have any duplicates? Yet I didn’t implement any specific code to enforce that. How could it work anyway? For most attributes, a simple counting argument suffices: the puzzle knows about five values and needs to place them in somewhere, so it can only succeed if all set values are indeed distinct. For the attributes that are part of the queries, it’s more of structural luck. We can indeed verify we have a solution with the four constrained attributes plus one placeholder, but nothing prevented the inference engine from yielding a solution with a duplicate attribute and no placeholder, provided such a solution was feasible.
• It’s so much faster than the brute-force version I can’t even reliably time it.

Reflecting on search

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.