How to solve the Zebra puzzle in Clojure
The Zebra puzzle is a common type of logical puzzles. When I was young, I solved tons of them, but I didn’t know how they were called. I read about the exact term first in this article: https://waitbutwhy.com/table/zebra-puzzle
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.
(defrecord Person [place color nation pet drink cigarettes])(def zebra-properties {
:place [1 2 3 4 5]
:nation ["Norwegian" "Ukrainian" "Japanese" "Spaniard" "English"]
:color ["Red" "Green" "Yellow" "Ivory" "Blue"]
:pet ["Dog" "Snail" "Fox" "Zebra" "Horse"]
:drink ["Coffee" "Tea" "Water" "Milk" "Orange Juice"]
:cigarettes ["Lucky Strike" "Chesterfield" "Kool" "Parliament" "Old Gold"]
})
Then I generated all the possible persons:
(defn assoc-Person [elemkey input]
(flatten
(map
(fn [x]
(map
(fn [y]
(assoc x elemkey y)
)
(elemkey zebra-properties)
)
)
input
)))(def empty-Person (Person. 0 "" "" "" "" ""))(def zebra-all-persons
(-> [empty-Person]
((partial assoc-Person :place ))
((partial assoc-Person :nation ))
((partial assoc-Person :color ))
((partial assoc-Person :pet ))
((partial assoc-Person :cigarettes ))
((partial assoc-Person :drink ))
))(count zebra-all-persons)
The last “count” line shows “15625” — so far, so good! Let’s write the rules:
(defn person-rule [item key1 value1 key2 value2]
(or
(and (not= (key1 item) value1) (not= (key2 item) value2))
(and (= (key1 item) value1) (= (key2 item) value2))
))(defn person-rule2 [item ]
(person-rule item :nation "English" :color "Red"))(defn person-rule3 [item]
(person-rule item :nation "Spaniard" :pet "Dog"))(defn person-rule4 [item]
(person-rule item :color "Green" :drink "Coffee"))(defn person-rule5 [item]
(person-rule item :nation "Ukrainian" :drink "Tea"))(defn person-rule6 [item]
(not
(or
(and (= (:place item) 5) (= (:color item) "Ivory" ))
(and (= (:place item) 1) (= (:color item) "Green" ))
)))(defn person-rule7 [item]
(person-rule item :cigarettes "Old Gold" :pet "Snail"))(defn person-rule8 [item]
(person-rule item :cigarettes "Kool" :color "Yellow"))(defn person-rule9 [item]
(person-rule item :place 3 :drink "Milk"))(defn person-rule10 [item]
(person-rule item :place 1 :nation "Norwegian"))(defn person-rule11 [item]
(not
(and (= (:cigarettes item) "Chesterfield") (= (:pet item) "Fox" ))))(defn person-rule12 [item]
(not
(and (= (:cigarettes item) "Kool") (= (:pet item) "Horse" ))))(defn person-rule13 [item]
(person-rule item :cigarettes "Lucky Strike" :drink "Orange Juice"))(defn person-rule14 [item]
(person-rule item :cigarettes "Parliament" :nation "Japanese"))(defn person-rule15 [item]
(person-rule item :place 2 :color "Blue"))
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:
(def filtered-persons
(-> zebra-all-persons((partial filter person-rule2))
((partial filter person-rule3))
((partial filter person-rule4))
((partial filter person-rule5))
((partial filter person-rule6))
((partial filter person-rule7))
((partial filter person-rule8))
((partial filter person-rule9))
((partial filter person-rule10))
((partial filter person-rule11))
((partial filter person-rule12))
((partial filter person-rule13))
((partial filter person-rule14))
((partial filter person-rule15))
))(count filtered-persons)
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:
(def grouped-filtered-persons (map (fn [x] (filter (fn [y] (= (:place y) x)) filtered-persons))
(:place zebra-properties)))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:
(defn conflicts? [group]
(apply distinct? (flatten (map (fn [x] (.values x)) group))))(def unconflicting-groups (filter conflicts?
(for [first (first grouped-filtered-persons)
second (second grouped-filtered-persons)
third (nth grouped-filtered-persons 2)
fourth (nth grouped-filtered-persons 3)
fifth (nth grouped-filtered-persons 4)]
(vector first second third fourth fifth))))(count unconflicting-groups)
Woo! We have only 104 groups remaining! Let’s create the neighbor constraints on the valid groups:
(defn get-person-from-group [group key value]
(first (filter (fn[x] (= (key x) value)) group)))(defn neighbors? [person1 person2]
(or
(=
(inc (:place person1))
(:place person2))
(=
(inc (:place person2))
(:place person1))
))(defn group-rule1 [group]
(=
(inc (:place (get-person-from-group group :color "Ivory")))
(:place (get-person-from-group group :color "Green"))
))(defn group-rule2 [group]
(neighbors?
(get-person-from-group group :cigarettes "Chesterfield")
(get-person-from-group group :pet "Fox")))(defn group-rule3 [group]
(neighbors?
(get-person-from-group group :cigarettes "Kool")
(get-person-from-group group :pet "Horse")))
And apply them:
(-> unconflicting-groups
((partial filter group-rule1))
((partial filter group-rule2))
((partial filter group-rule3)))And voilá! We have only one group left, which is the exact solution to the problem. Well done!