How to solve the Zebra puzzle in Clojure

The puzzles I used to have solved had only 4 or 5 dimensions, but that particular instance mentioned in the article (incorrectly called the Einstein’s Riddle) has 6 dimensions. I am able to solve lesser dimensions, but 6? Needs a lot of thinking and sketching. As a developer, I’m too lazy for handling that amount of writing, but let’s write a program which solves it for me! And because I’m learning Clojure now, let’s try to do it in Clojure.

How should I start? Let’s generate all the possible solutions and filter out the wrong ones. In the end, one should prevail. Sounds easy, doesn’t it? But how many solutions are possible? Well, there are 6 dimensions, each dimension has 5 possible values, so there are 5⁶ = 15625 possible persons. We have to pick 5 of them for each possible solution, so there are binomial(15625,5) = 7756055513916018750 possible groups. Maybe generating all of them is not the right solution. But wait! Some of these are not even valid solutions! We have counted all the groups where two persons can live in the same house or have the same pet! All of these are invalid solutions.

Then how many valid solutions can we have? If we fix the first dimension, then we have 5 dimensions to permutate. All of these dimensions has 5! = 120 permutations, so there are 120⁵ = 24883200000 possible valid solutions, which are way less than in the previous case, but still a lot!

Can we tackle the problem from a different aspect? I realized that most of the constraints are affecting only one person (except the “neighbor” constraints, rule 6, 11, 12, and 15). For example if somebody smokes Kool, they can only live in yellow house. That means I can apply filters on the possible persons group first, and then select the solution groups from the filtered set.

Let’s see how I have achieved that.

First, I created the Clojure record and the data structure which holds the different values in the dimension.

Then I generated all the possible persons:

The last “count” line shows “15625” — so far, so good! Let’s write the rules:

Even if Rule 6 is a neighbor constraint, it affects the individual persons: Green cannot be the first house and Ivory cannot be the last.

Rule 11 and 12 are similar: they are neighbors, therefore Chesterfield smoker cannot have a fox, and Kool smoker cannot have a horse.

As for Rule 15, I cheated a bit: Rule 10 and 15 gives you a simple deduction, and I used that as a constraint for this one.

Let’s apply the filters:

So we have 58 possible persons, and binomial(58,5) is 4582116 which is definitely doable.

Let’s group these persons by their house number, we will pick one person from each group to generate the possible solutions:

But hey, we’ve forgotten something! Even if the first dimension (the house number) doesn’t conflict, the others still can! How can we generate only valid possible solutions? The solution is a bit tricky:

Woo! We have only 104 groups remaining! Let’s create the neighbor constraints on the valid groups:

And apply them:

And voilá! We have only one group left, which is the exact solution to the problem. Well done!

Related posts:

Tengo que admitir que el título no hace justicia al enorme trabajo y “seso” invertido en el desarrollo estas tecnologías. Es tan injusto como insinuar rivalidades en el ámbito de la música con un…

Story by Anonymous for The Better Because Project

Sitting on the edge. Do I like sitting on the edge? Do I… why would I like it? It’s full of danger, anticipation, doubt vying towards self-doubt, anger, quick thinking, and of course, injury-prone…