Solving Einstein’s Puzzle with Constraint Programming

The following puzzle is a well-known meme in social networks. It is said to have been invented by young Einstein and back in the days I was ambitious enough to solve it by hand (you should try too!).

Yet, even simpler is to use Constraint Programming (CP). An excellent choice for doing that is MiniZinc, a free and open-source constraint modelling language. And the best thing is that you can control it by R! If you want to see how, read on!

Einstein’s puzzle (a.k.a. Zebra puzzle) goes like this:

1. There are five houses.
2. The English man lives in the red house.
3. The Swede has a dog.
4. The Dane drinks tea.
5. The green house is immediately to the left of the white house.
6. They drink coffee in the green house.
7. The man who smokes Pall Mall has birds.
8. In the yellow house they smoke Dunhill.
9. In the middle house they drink milk.
10. The Norwegian lives in the first house.
11. The man who smokes Blend lives in the house next to the house with cats.
12. In a house next to the house where they have a horse, they smoke Dunhill.
13. The man who smokes Blue Master drinks beer.
14. The German smokes Prince.
15. The Norwegian lives next to the blue house.
16. They drink water in a house next to the house where they smoke Blend.

The question is, who owns the zebra?

If you want to try it yourself, feel free!

The big idea of constraint programming is that one does not specify a step or sequence of steps to execute, but rather the properties of a solution to be found (which is pretty cool, right!).

The way to code this in MiniZinc is pretty straightforward although it would be beyond the scope of this post to give an introduction to constraint programming. MiniZinc itself comes with excellent documentation and the following code for our problem can be found here: Rosetta Code: Zebra puzzle.

%Solve Zebra Puzzle. Nigel Galloway, August 27th., 2019
include "alldifferent.mzn";
enum N={English,Swedish,Danish,German,Norwegian};
enum I={Tea,Coffee,Milk,Beer,Water};
enum G={Dog,Birds,Cats,Horse,Zebra};
enum E={Red,Green,White,Blue,Yellow};
enum L={PallMall,Dunhill,BlueMaster,Prince,Blend};
array[1..5] of var N: Nz; constraint alldifferent(Nz); constraint Nz[1]=Norwegian;                   %The Norwegian lives in the first house.
array[1..5] of var I: Iz; constraint alldifferent(Iz); constraint Iz[3]=Milk;                        %In the middle house they drink milk.
array[1..5] of var G: Gz; constraint alldifferent(Gz);
array[1..5] of var E: Ez; constraint alldifferent(Ez);
array[1..5] of var L: Lz; constraint alldifferent(Lz);
constraint exists(n in 1..5)(Nz[n]=English /\ Ez[n]=Red);                                            %The English man lives in the red house
constraint exists(n in 1..5)(Nz[n]=Swedish /\ Gz[n]=Dog);                                            %The Swede has a dog.
constraint exists(n in 1..5)(Nz[n]=Danish  /\ Iz[n]=Tea);                                            %The Dane drinks tea.
constraint exists(n in 1..4)(Ez[n]=Green /\ Ez[n+1]=White);                                          %The green house is immediately to the left of the white house.
constraint exists(n in 1..5)(Ez[n]=Green /\ Iz[n]=Coffee);                                           %They drink coffee in the green house.
constraint exists(n in 1..5)(Lz[n]=PallMall /\ Gz[n]=Birds);                                         %The man who smokes Pall Mall has birds
constraint exists(n in 1..5)(Ez[n]=Yellow /\ Lz[n]=Dunhill);                                         %In the yellow house they smoke Dunhill.
constraint exists(n in 1..4)((Lz[n]=Blend /\ Gz[n+1]=Cats) \/ (Lz[n+1]=Blend /\ Gz[n]=Cats));        %The man who smokes Blend lives in the house next to the house with cats.
constraint exists(n in 1..4)((Gz[n]=Horse /\ Lz[n+1]=Dunhill) \/ (Gz[n+1]=Horse /\ Lz[n]=Dunhill));  %In a house next to the house where they have a horse, they smoke Dunhill.
constraint exists(n in 1..5)(Lz[n]=BlueMaster /\ Iz[n]=Beer);                                        %The man who smokes Blue Master drinks beer.
constraint exists(n in 1..5)(Nz[n]=German /\ Lz[n]=Prince);                                          %The German smokes Prince.
constraint exists(n in 1..4)((Nz[n]=Norwegian /\ Ez[n+1]=Blue) \/ (Nz[n+1]=Norwegian /\ Ez[n]=Blue));%The Norwegian lives next to the blue house.
constraint exists(n in 1..4)((Lz[n]=Blend /\ Iz[n+1]=Water) \/ (Lz[n+1]=Blend /\ Iz[n]=Water));      %They drink water in a house next to the house where they smoke Blend. 
var 1..5: n;
constraint Gz[n]=Zebra; 
solve satisfy;
output ["The "++show(Nz[n])++" owns the zebra"++"\n\n"++show(Nz)++"\n"++show(Iz)++"\n"++show(Gz)++"\n"++show(Ez)++"\n"++show(Lz)++"\n"];

To call this from R we need to install MiniZinc first (from here: MiniZinc), save the above code in a file called zebra.mzn and adjust the paths in the following script accordingly. The R code itself is just base R and very minimalistic (Thank you to one of the giants of CP, Hakan Kjellerstrand, for his help!):

# Flags:
#  -a: show all solutions
#  -s: show statistics
#  -n <n>: show n solutions (0: all)
#  --solver <solver>: use solver <solver>

minizinc <- "C:/Program\ Files/MiniZinc/minizinc" # adjust accordingly
model <- "C:/Users/Holger/Dropbox/MiniZinc/zebra.mzn" # adjust accordingly

MiniZinc <- function(model, minizinc_path = minizinc, flags = "-a -s") {
  out <- system(paste(shQuote(minizinc_path), flags, shQuote(model)), intern = TRUE)
  cat(out, sep = "\n")
}

MiniZinc(model, flags = "-a")
## The German owns the zebra
## 
## [Norwegian, Danish, English, German, Swedish]
## [Water, Tea, Milk, Coffee, Beer]
## [Cats, Horse, Birds, Zebra, Dog]
## [Yellow, Blue, Red, Green, White]
## [Dunhill, Blend, PallMall, Prince, BlueMaster]
## ----------
## ==========

Now you know: The German owns the zebra! If you arrived at the same solution by hand: Good for you!

In any case, you can use this as a template to start your own experiments with constraint programming and analyze the results further with R!