Problem (Life International, 1962). Five houses in a row, each of a different colour, with owners of different nationalities, drinks, cigarette brands and pets.
- The Englishman lives in the red house. 2. The Spaniard owns the dog. 3. Coffee is drunk in the green house. 4. The Ukrainian drinks tea. 5. The green house is immediately to the right of the ivory house. 6. The Old Gold smoker owns snails. 7. Kools are smoked in the yellow house. 8. Milk is drunk in the middle house. 9. The Norwegian lives in the first house. 10. The Chesterfield smoker lives next to the man with the fox. 11. Kools are smoked next to the house with the horse. 12. The Lucky Strike smoker drinks orange juice. 13. The Japanese smokes Parliaments. 14. The Norwegian lives next to the blue house.
Who drinks water? Who owns the zebra?
Answer. The unique solution:
| House | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| colour | yellow | blue | red | ivory | green |
| nationality | Norwegian | Ukrainian | Englishman | Spaniard | Japanese |
| drink | water | tea | milk | orange juice | coffee |
| smoke | Kools | Chesterfield | Old Gold | Lucky Strike | Parliament |
| pet | fox | horse | snails | dog | zebra |
The Norwegian drinks water and the Japanese owns the zebra.
| Approach | How | When |
|---|---|---|
| logic grid (by hand) | a yes/no table for every pair of values; propagate eliminations and “only one left” | human solving |
| permutation backtracking | assign one category at a time as a permutation of houses ( each), check every clue as soon as its categories are assigned | categories of : instant |
| constraint propagation | keep domains, prune with all-different and arc consistency | larger puzzles |
| 2-SAT | if every decision is boolean and every clue is a 2-clause (” or “) | linear time, see SCC and 2-SAT |
| general CSP | NP-complete (graph 3-colouring is a special case) | expect search |
// Constraint satisfaction over permutations: k categories, n values each, every value in a distinct house.
// pos[c][v] = house of value v of category c. Each constraint lists the categories it reads (bitmask).
struct PermCSP {
using Pos = vector<vector<int>>;
int k, n; Pos pos; vector<pair<int, function<bool(const Pos&)>>> cons; vector<Pos> sols;
PermCSP(int k, int n) : k(k), n(n), pos(k) {}
void add(int mask, function<bool(const Pos&)> f) { cons.push_back({mask, f}); }
void solve(int c = 0) {
if (c == k) { sols.push_back(pos); return; }
vector<int> p(n); iota(all(p), 0);
do {
pos[c] = p; bool ok = true;
for (auto& [m, f] : cons) // check a clue once its last category is placed
if ((m >> c & 1) && !(m >> (c + 1)) && !f(pos)) { ok = false; break; }
if (ok) solve(c + 1);
} while (next_permutation(all(p)));
}
};
PermCSP einstein() {
enum { NAT, COL, DRK, SMK, PET }; // categories
enum { ENG = 0, SPA, UKR, NOR, JAP }; // nationality values
enum { RED = 0, GRN, IVO, YEL, BLU }; // colours
enum { COF = 0, TEA, MLK, OJ, WAT }; // drinks
enum { OG = 0, KOO, CHE, LS, PAR }; // smokes
enum { DOG = 0, SNA, FOX, HOR, ZEB }; // pets
PermCSP P(5, 5); using Pos = PermCSP::Pos;
auto same = [&](int c1, int v1, int c2, int v2) { P.add(1 << c1 | 1 << c2, [=](const Pos& p) { return p[c1][v1] == p[c2][v2]; }); };
auto next = [&](int c1, int v1, int c2, int v2) { P.add(1 << c1 | 1 << c2, [=](const Pos& p) { return abs(p[c1][v1] - p[c2][v2]) == 1; }); };
same(NAT, ENG, COL, RED); same(NAT, SPA, PET, DOG); same(DRK, COF, COL, GRN); same(NAT, UKR, DRK, TEA);
P.add(1 << COL, [=](const Pos& p) { return p[COL][GRN] == p[COL][IVO] + 1; });
same(SMK, OG, PET, SNA); same(SMK, KOO, COL, YEL);
P.add(1 << DRK, [=](const Pos& p) { return p[DRK][MLK] == 2; });
P.add(1 << NAT, [=](const Pos& p) { return p[NAT][NOR] == 0; });
next(SMK, CHE, PET, FOX); next(SMK, KOO, PET, HOR); same(SMK, LS, DRK, OJ); same(NAT, JAP, SMK, PAR); next(NAT, NOR, COL, BLU);
P.solve();
return P;
}Proof: the search is exhaustive and the solution is unique
Exhaustive. A full assignment is a choice of one permutation per category; the recursion enumerates all of them in a tree, cutting a branch only when a clue whose categories are all assigned already fails. A failed clue stays failed in every completion (it reads only assigned categories), so no solution is cut; every leaf that is reached has passed every clue (each clue is checked exactly at the level of its highest category). So
solsis exactly the set of solutions, and for the clues above it has size 1, the table shown.By hand. Clue 9 puts the Norwegian in house 1 and clue 14 makes house 2 blue. Clue 5 leaves (ivory, green) or ; in both cases the red house (the Englishman’s) is not house 1, so house 1 is yellow, smokes Kools (7), and the horse is in house 2 (11). Suppose (ivory, green) : red is 5; the Ukrainian drinks tea, so he is neither in 3 (milk) nor in 4 (coffee), hence in 2; house 1 smokes Kools so it does not drink orange juice (12): it drinks water and house 5 drinks orange juice and smokes Lucky Strike. The Spaniard and the Japanese share houses 3 and 4, the Japanese smoking Parliament (13), so Old Gold and Chesterfield go to house 2 and the Spaniard’s house; house 2 keeps the horse, so it is not Old Gold (6), so the Spaniard smokes Old Gold and owns snails, contradicting clue 2. Hence (ivory, green) , red is 3, and clues 4, 12, 13, 6, 2, 10 force the rest by elimination. Checked:
einstein()returns exactly one solution; the solver also agrees with brute force (all assignments, clues checked at the end) on random puzzles with 3 categories of 3 houses.