This is the twenty seventh part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Hi! Today we are going to solve Einstein’s five houses riddle using ILP!

Table of Contents

Introduction

In the riddle we have five houses. Person living in every house can be described using five traits (nationality, favorite drink, spoked stuff, color of the house, and favorite pet). For every trait we have five different values: there are five colors, five animals, five drinks etc. We are given some logical constraints describing the persons and wee need to find the final matching between houses and traits. Looks like ideal case for our ILP program!

Matrix of traits

We have the following traits:

$\begin{gather*} \label{tab:sets} \begin{tabular}{|c|c|c|c|c|c|} \hline Trait & 1 & 2 & 3 & 4 & 5 \\ \hline Color & Yellow & Blue & Red & Ivory & Green\\ \hline Nationality & Norwegian & Ukrainian & Englishman & Spaniard & Japanese\\ \hline Drink & Water & Tea & Milk & Orange juice & Coffee\\ \hline Smoke & Kools & Chesterfield & Old Gold & Lucky Strike & Parliament\\ \hline Pet & Fox & Horse & Snails & Dog & Zebra \hline \end{tabular} \end{gather*}$

We define the following binary variables:

$\begin{gather*} \text{colors: }c_{\text{\#house}, i} \\ \text{nationalities: } n_{\text{\#house}, i} \\ \text{drinks: } d_{\text{\#house}, i} \\ \text{smokes: } s_{\text{\#house}, i} \\ \text{pets: } p_{\text{\#house}, i} \end{gather*}$

Every variable answers the question if the associated house has the associated trait set to true. For instance, $c_{1, 2}$ set to true means that the house number $1$ is blue, whereas $s_{4, 1}$ would mean that the guy living in house number $4$ smokes Kools.

Constraints

We need to add basic constraints that one trait is associated with exactly one house:

$\begin{gather*} \displaystyle\mathop{\forall}_{i} \displaystyle\mathop{\sum}_{j} c_{i, j} = 1\\ \displaystyle\mathop{\forall}_{i} \displaystyle\mathop{\sum}_{j} c_{j, i} = 1\\ \displaystyle\mathop{\forall}_{i} \displaystyle\mathop{\sum}_{j} n_{i, j} = 1\\ \displaystyle\mathop{\forall}_{i} \displaystyle\mathop{\sum}_{j} n_{j, i} = 1\\ \displaystyle\mathop{\forall}_{i} \displaystyle\mathop{\sum}_{j} d_{i, j} = 1\\ \displaystyle\mathop{\forall}_{i} \displaystyle\mathop{\sum}_{j} d_{j, i} = 1\\ \displaystyle\mathop{\forall}_{i} \displaystyle\mathop{\sum}_{j} s_{i, j} = 1\\ \displaystyle\mathop{\forall}_{i} \displaystyle\mathop{\sum}_{j} s_{j, i} = 1\\ \displaystyle\mathop{\forall}_{i} \displaystyle\mathop{\sum}_{j} p_{i, j} = 1\\ \displaystyle\mathop{\forall}_{i} \displaystyle\mathop{\sum}_{j} p_{j, i} = 1\\ \end{gather*}$

Now we can add formulas for constraints specified in the riddle.

The Englishman lives in the red house.

$\begin{gather*} \displaystyle\mathop{\forall}_{i} n_{i, 3} = c_{i,3} \end{gather*}$

The Spaniard owns the dog.

$\begin{gather*} \displaystyle\mathop{\forall}_{i} n_{i, 4} = p_{i,4} \end{gather*}$

Coffee is drunk in the green house.

$\begin{gather*} \displaystyle\mathop{\forall}_{i} d_{i, 5} = c_{i,5} \end{gather*}$

The Ukrainian drinks tea.

$\begin{gather*} \displaystyle\mathop{\forall}_{i} n_{i, 2} = d_{i,2} \end{gather*}$

The green house is immediately to the right of the ivory house.

$\begin{gather*} \displaystyle\mathop{\forall}_{i} c_{i+1, 5} = c_{i,4} \end{gather*}$

The Old Gold smoker owns snails.

$\begin{gather*} \displaystyle\mathop{\forall}_{i} s_{i, 3} = p_{i,3} \end{gather*}$

Kools are smoked in the yellow house.

$\begin{gather*} \displaystyle\mathop{\forall}_{i} s_{i, 1} = c_{i,1} \end{gather*}$

Milk is drunk in the middle house.

$\begin{gather*} d_{3, 3} = 1 \end{gather*}$

The Norwegian lives in the first house.

$\begin{gather*} n_{1, 1} = 1 \end{gather*}$

The man who smokes Chesterfields lives in the house next to the man with the fox.

$\begin{gather*} \displaystyle\mathop{\sum}_{i} s_{i, 2} \wedge p_{i \pm 1,1} = 1 \end{gather*}$

Kools are smoked in the house next to the house where the horse is kept.

$\begin{gather*} \displaystyle\mathop{\sum}_{i} s_{i, 1} \wedge p_{i \pm 1,2} = 1 \end{gather*}$

The Lucky Strike smoker drinks orange juice.

$\begin{gather*} \displaystyle\mathop{\forall}_{i} s_{i, 4} = d_{i,4} \end{gather*}$

The Japanese smokes Parliaments.

$\begin{gather*} \displaystyle\mathop{\forall}_{i} n_{i, 5} = s_{i,5} \end{gather*}$

The Norwegian lives next to the blue house.

$\begin{gather*} \displaystyle\mathop{\sum}_{i} n_{i, 1} \wedge c_{i \pm 1,2} = 1 \end{gather*}$

Summary

As we can see it is very easy to solve the Einstein’s riddle using ILP. Most of the constraints are straightforward, only constraints of type “something is in the house next to” are a bit more difficult.