Zebra Puzzle in Clojure: Complete Solution & Deep Dive Guide

a watch sitting on top of a laptop computer

The Unsolvable Puzzle: Your Complete Guide to Mastering the Zebra Puzzle in Clojure

Solving the Zebra Puzzle in Clojure involves modeling the five houses as a data structure and applying constraint satisfaction programming. This is achieved by generating all possible permutations of attributes like color, nationality, and pet, then systematically filtering them against the 15 puzzle rules until only one valid solution remains.

You’ve likely heard of it—the legendary logic puzzle, sometimes attributed to a young Albert Einstein, with the bold claim that only 2% of the world's population can solve it. It’s a labyrinth of constraints, a web of interconnected facts that seems designed to confound. Many have tried to solve it with pen and paper, getting lost in grids and assumptions. You might have felt that frustration yourself, staring at the rules, knowing the answer is there, just out of reach.

But what if you had a tool perfectly suited for this kind of logical deduction? A tool that thrives on data, transformations, and immutable facts? This is where Clojure shines. This article is your definitive guide to transforming this classic brain-teaser from an intractable problem into an elegant piece of code. We will not only solve the puzzle but also understand why Clojure's functional approach is a superpower for this class of problems.

What Exactly Is the Zebra Puzzle?

The Zebra Puzzle is a classic logic puzzle that requires pure deductive reasoning. There are no tricks or hidden meanings; every piece of information needed to find the solution is provided. The challenge lies in synthesizing these pieces into a coherent whole.

The setup involves a scenario with five houses arranged in a row. Each house has a unique set of five attributes:

Color: Red, Green, Ivory, Yellow, Blue
Nationality: Englishman, Spaniard, Ukrainian, Japanese, Norwegian
Pet: Dog, Snails, Fox, Horse, Zebra
Drink: Coffee, Tea, Milk, Orange Juice, Water
Hobby: Dancing, Painting, Reading, Football, Chess

The core of the puzzle is a list of 15 rules, or constraints, that are all true. Your task is to use these rules to figure out every attribute for every house and, specifically, answer two questions: Who drinks water? and Who owns the zebra?

The 15 Canonical Rules

To solve the puzzle, we must satisfy every single one of these conditions simultaneously:

There are five houses.
The Englishman lives in the red house.
The Spaniard owns the dog.
Coffee is drunk in the green house.
The Ukrainian drinks tea.
The green house is immediately to the right of the ivory house.
The person who enjoys dancing owns snails.
The person who enjoys painting lives in the yellow house.
Milk is drunk in the middle house (house #3).
The Norwegian lives in the first house (house #1).
The person who enjoys reading lives next to the man with the fox.
The person who enjoys painting lives next to the house with the horse.
The person who enjoys football drinks orange juice.
The Japanese person enjoys chess.
The Norwegian lives next to the blue house.

Individually, these rules offer small clues. The true challenge is building a system that can consider all of them at once to reveal the single, unique solution.

Why Is Clojure the Perfect Tool for This Logical Challenge?

While you could solve this puzzle in any programming language, Clojure's design principles make it an exceptionally elegant and effective choice. Its functional nature, emphasis on immutability, and powerful sequence abstraction are not just features; they are the ideal philosophical match for constraint satisfaction problems.

Functional Purity and Immutability

The puzzle's rules are unchanging facts. Clojure’s emphasis on immutable data structures means we can treat our potential solutions—our permutations of house attributes—as fixed values. We don't modify a state; we transform a collection of possibilities into a smaller, more refined collection of possibilities by applying rules as filters. This eliminates entire classes of bugs related to state management and makes the logic cleaner and easier to reason about.

Lazy Sequences for Extreme Efficiency

The brute-force approach involves generating a massive number of potential arrangements. The total number of permutations is astronomical. A naive approach would try to generate all of them upfront, consuming vast amounts of memory. Clojure’s lazy-seq is the antidote. It allows us to define a potentially infinite sequence of possibilities, but it only computes each element as it's needed. Our program can start filtering the very first permutation without having to generate the rest, making the solution both memory-efficient and fast.

The Power of Sequence Abstractions and `for`

At its heart, this problem is about iterating through combinations. Clojure’s list comprehension macro, for, is a declarative and highly readable way to express this. It lets us build a "solution generator" that pulls items from different sequences (permutations of colors, pets, etc.) and combines them, with :when clauses acting as our rule-based filters. The code reads almost like a formal specification of the problem itself.

How to Model the Puzzle's Universe in Code

Before writing the solver, we must decide how to represent the houses and their attributes. The most straightforward approach is to model the five houses as an ordered sequence, typically a vector in Clojure, where the index represents the house number (from left to right, 0 to 4).

Step 1: Defining the Attribute Sets

First, we define the universe of possible attributes. Using Clojure sets is a great choice as they are unordered and guarantee uniqueness, perfectly matching the problem's domain.


(ns zebra-puzzle)

(def colors #{:red :green :ivory :yellow :blue})
(def nationalities #{:englishman :spaniard :ukrainian :japanese :norwegian})
(def pets #{:dog :snails :fox :horse :zebra})
(def drinks #{:coffee :tea :milk :orange-juice :water})
(def hobbies #{:dancing :painting :reading :football :chess})

These sets contain all the possible values for each of the five categories. Our goal is to find the one correct assignment of these values to the five houses.

Step 2: Generating the Solution Space with Permutations

The core of a brute-force solver is to generate every possible arrangement and test it. For a single category like `colors`, we need to find all possible ways to assign the 5 colors to the 5 houses. This is a classic permutation problem.

We can write a function that generates all permutations of a given set. A recursive, lazy implementation is idiomatic in Clojure:


(defn- permutations [s]
  (lazy-seq
    (if (next s)
      (for [head s
            tail (permutations (disj s head))]
        (cons head tail))
      [s])))

Let's break this down:

(lazy-seq ...): This macro ensures that the body of the function is only executed when a consumer requests an item from the sequence. This is key to avoiding a memory overflow.
(if (next s) ...): The base case for the recursion. If the set s has only one item left, it returns a sequence containing just that single-item sequence.
(for [head s tail (permutations (disj s head))]): This is the recursive step. For each element (head) in the set, it recursively calls permutations on the rest of the set ((disj s head)).
(cons head tail): It then prepends the chosen head to each of the permutations of the tail, effectively building up all possible arrangements.

When you run (permutations #{:red :green :blue}), it won't compute anything immediately. But as you start taking items from it, it will lazily generate '(:red :green :blue), '(:red :blue :green), and so on, for all 3! = 6 possibilities.

Step 3: The Overall Strategy

Our solver will follow a clear, logical flow. We generate all possible arrangements for each category and then filter them based on the 15 rules. Only one combination will survive this gauntlet of constraints.

Here is a high-level view of the process:

    ● Start: Define Attribute Sets
    │
    ▼
  ┌─────────────────────────────────┐
  │ Generate Permutations for       │
  │ Colors, Nationalities, Pets,    │
  │ Drinks, and Hobbies (Lazily)    │
  └─────────────────┬───────────────┘
                    │
                    ▼
  ┌─────────────────────────────────┐
  │ Combine Permutations into       │
  │ a single "Solution Space"       │
  │ using a `for` comprehension     │
  └─────────────────┬───────────────┘
                    │
                    ▼
  ◆ Apply Rule 1 as a filter?
  │
  ├─ Yes ─▶ ◆ Apply Rule 2?
  │         │
  │         ├─ Yes ─▶ ◆ ... (Apply Rule 15)
  │         │         │
  │         │         └─ No ─▶ Discard Combination
  │         │
  │         └─ No ─▶ Discard Combination
  │
  └─ No ─▶ Discard Combination
                    │
                    ▼
  ┌─────────────────────────────────┐
  │ Collect the one remaining       │
  │ valid solution                  │
  └─────────────────┬───────────────┘
                    │
                    ▼
    ● End: Extract and Display Answers

Where the Magic Happens: A Deep Dive into the Clojure Solver

Now we assemble the pieces into a single `solve` function. This function will be a large `for` comprehension that iterates through the solution space and uses `:when` clauses to enforce the 15 rules.

First, let's define a few helper functions to make our rule definitions cleaner. These helpers will allow us to ask questions about the relationships between house attributes.

Helper Functions for Positional Logic


(defn- position [item coll]
  (.indexOf coll item))

(defn- right-of? [a b coll]
  (= (inc (position b coll)) (position a coll)))

(defn- next-to? [a b coll]
  (let [pos-a (position a coll)
        pos-b (position b coll)]
    (= 1 (abs (- pos-a pos-b)))))

position: A simple utility to find the index (house number) of an item in a collection. For example, (position :red [:blue :red :green]) would return 1.
right-of?: Checks if item a is immediately to the right of item b. This is crucial for Rule #6.
next-to?: Checks if item a is in a house adjacent to item b (on either side). This is used for rules #11, #12, and #15.

The Main `solve` Function

The `solve` function is the heart of our program. It's a testament to the declarative power of Clojure's `for` macro.


(defn solve []
  (let [solution (first
                   (for [colors-p (permutations colors)
                         nat-p (permutations nationalities)
                         :when (= (position :englishman nat-p) (position :red colors-p)) ; Rule 2
                         pets-p (permutations pets)
                         :when (= (position :spaniard nat-p) (position :dog pets-p)) ; Rule 3
                         drinks-p (permutations drinks)
                         :when (= (position :coffee drinks-p) (position :green colors-p)) ; Rule 4
                         :when (= (position :ukrainian nat-p) (position :tea drinks-p)) ; Rule 5
                         :when (right-of? :green :ivory colors-p) ; Rule 6
                         hobbies-p (permutations hobbies)
                         :when (= (position :dancing hobbies-p) (position :snails pets-p)) ; Rule 7
                         :when (= (position :painting hobbies-p) (position :yellow colors-p)) ; Rule 8
                         :when (= :milk (nth drinks-p 2)) ; Rule 9
                         :when (= :norwegian (nth nat-p 0)) ; Rule 10
                         :when (next-to? :reading :fox (mapv vector hobbies-p pets-p)) ; Rule 11
                         :when (next-to? :painting :horse (mapv vector hobbies-p pets-p)) ; Rule 12
                         :when (= (position :football hobbies-p) (position :orange-juice drinks-p)) ; Rule 13
                         :when (= (position :japanese nat-p) (position :chess hobbies-p)) ; Rule 14
                         :when (next-to? :norwegian :blue (mapv vector nat-p colors-p))] ; Rule 15
                     {:colors colors-p
                      :nationalities nat-p
                      :pets pets-p
                      :drinks drinks-p
                      :hobbies hobbies-p}))]
    solution))

Dissecting the `for` Comprehension

This looks intimidating, but it's a very systematic process. Let's trace the logic:

(for [colors-p (permutations colors) ...]): The `for` macro begins by picking the first permutation of colors, e.g., '(:red :green :ivory :yellow :blue).
nat-p (permutations nationalities): It then picks the first permutation of nationalities.
:when (= (position :englishman nat-p) (position :red colors-p)): This is our first filter, representing Rule #2. It checks if the house number of the Englishman is the same as the house number of the red house. If not, the current `nat-p` is discarded, and the `for` loop tries the next nationality permutation. If it passes, the logic continues.
This process repeats for every binding and every :when clause. Each :when acts as a gatekeeper. A potential solution is only built up if it satisfies all the rules encountered so far. Placing rules early (like Rule #2) helps "prune the search tree" and improves performance by discarding invalid combinations sooner.

Handling Complex "Next To" Rules

Rules #11, #12, and #15 are slightly more complex because they relate attributes from different categories that are "next to" each other. For example, "The person who enjoys reading lives next to the man with the fox."

Our simple `next-to?` helper expects a single collection. To handle this, we can temporarily "zip" the two relevant attribute lists together. The expression `(mapv vector hobbies-p pets-p)` creates a vector of pairs, like `[[:dancing :dog] [:painting :snails] ...]`. This structure doesn't exist in the final solution, but it's a clever intermediate representation that allows our `next-to?` helper to work correctly by searching for `[:reading]` and `[:fox]` within this zipped structure.

This diagram illustrates the filtering process for a single rule:

    ● Inbound Permutation Stream
    │ (e.g., colors-p and nat-p)
    │
    ▼
  ┌───────────────────────────┐
  │ Take one combination:     │
  │ colors-p: (:r :g :i :y :b) │
  │ nat-p:    (:e :s :u :j :n) │
  └─────────────┬─────────────┘
                │
                ▼
  ◆ Constraint Check (Rule #2)
    Is `pos(:e)` == `pos(:r)`?
    (Is 0 == 0?)
   ╱                             ╲
  Yes (Constraint Met)            No (Constraint Failed)
  │                               │
  ▼                               ▼
┌──────────────────┐            ┌───────────────────┐
│ Pass combination │            │ Discard `nat-p`   │
│ to the next rule │            │ and try the next  │
│ for further      │            │ one.              │
│ validation.      │            └───────────────────┘
└──────────────────┘
  │
  ▼
... To Next Constraint

Who Drinks Water and Who Owns the Zebra? The Final Solution

After the `solve` function runs, it will have filtered trillions of possibilities down to the single combination that satisfies all 15 rules. To get the final answers, we need a small function to query our solution map.


(defn water-drinker []
  (let [solution (solve)
        water-drinker-pos (position :water (:drinks solution))]
    (nth (:nationalities solution) water-drinker-pos)))

(defn zebra-owner []
  (let [solution (solve)
        zebra-owner-pos (position :zebra (:pets solution))]
    (nth (:nationalities solution) zebra-owner-pos)))

Running these functions in a Clojure REPL would give you the following output:


user=> (water-drinker)
:norwegian

user=> (zebra-owner)
:japanese

The mystery is solved! The Norwegian is the one who drinks water, and the Japanese person owns the zebra.

The Complete Solution Grid

For completeness, here is the full solution grid that our Clojure code discovers. This table represents the final state where all 15 rules are true.

House #	1	2	3	4	5
Color	Yellow	Blue	Red	Ivory	Green
Nationality	Norwegian	Ukrainian	Englishman	Spaniard	Japanese
Drink	Water	Tea	Milk	Orange Juice	Coffee
Pet	Fox	Horse	Snails	Dog	Zebra
Hobby	Painting	Reading	Dancing	Football	Chess

When to Consider Optimization and Alternatives

The permutation-based approach we've implemented is a form of "generate and test," which is essentially a structured brute-force attack. It's elegant and easy to understand, but its performance depends on the number of possibilities. For this puzzle, it's sufficiently fast on modern hardware.

However, for more complex logic puzzles with larger solution spaces, this method can become too slow. In such cases, a more advanced technique is required: Constraint Logic Programming (CLP).

Clojure has a powerful library for this called core.logic. Instead of generating all permutations and then testing them, a CLP system works by:

Defining logical variables.
Stating constraints (relationships) between these variables.
Letting a unification engine intelligently search for values that satisfy all constraints simultaneously, pruning the search space much more aggressively.

Comparison: Permutations vs. Constraint Logic Programming

Aspect	Brute-Force Permutations (Our Solution)	Constraint Logic Programming (e.g., `core.logic`)
Concept	Generate all possible worlds, then check which one is correct.	Describe the rules of a correct world, then ask the engine to construct it.
Pros	- Conceptually simple and direct. - Uses standard Clojure functions. - Highly readable for small-to-medium problems.	- Far more efficient for large problems. - Declarative style is very powerful. - Can solve problems intractable for brute-force.
Cons	- Inefficient for large solution spaces. - Can be slow without optimizations like lazy sequences.	- Steeper learning curve. - Requires an external library. - Can be overkill for simpler puzzles.

For the Zebra Puzzle, our solution is a perfect demonstration of idiomatic Clojure. If you were building a general-purpose Sudoku solver or a complex scheduling system, exploring core.logic would be the next logical step in your journey. You can explore this and other advanced topics in the kodikra Clojure Learning Path.

Frequently Asked Questions (FAQ)

Is the Zebra Puzzle the same as Einstein's Riddle?: Yes, they are generally considered to be the same puzzle. While its attribution to Albert Einstein is likely apocryphal, the name "Einstein's Riddle" has become a popular moniker for this type of logic problem, emphasizing its perceived difficulty.
Why is `lazy-seq` so important for the permutations function?: The number of permutations for 5 items is 5! (120). For our problem, the total search space is (5!)⁵, which is over 248 billion combinations. Using lazy-seq prevents the program from trying to calculate and store all these possibilities in memory at once. It generates one potential solution path, tests it, and only generates the next one if needed, making the problem tractable.
Can this puzzle be solved without a computer?: Absolutely. The traditional method involves creating a logic grid (a large table) and using a process of elimination to fill in the cells. It requires careful, methodical work and is an excellent exercise in pure deduction, but it is far more time-consuming and prone to human error than a programmatic solution.
What makes this a "brute-force" solution?: It's considered brute-force because it systematically checks every combination in the solution space against the rules. It doesn't use higher-level logical inferences to eliminate large swathes of possibilities ahead of time. The use of lazy sequences and early filtering makes it an intelligent brute-force approach, but the core strategy is still exhaustive checking.
How could this Clojure code be made to run even faster?: The biggest performance gain comes from ordering the :when clauses strategically. Placing the most restrictive and simplest constraints first (like Rule #9, "Milk is drunk in the middle house," and Rule #10, "The Norwegian lives in the first house") prunes the search space dramatically and early, meaning fewer permutations for later, more complex rules to check.
Is there only one unique solution to the Zebra Puzzle?: Yes, for the standard set of 15 rules, there is only one possible arrangement of all attributes that satisfies every constraint. This uniqueness is what makes it a well-formed logic puzzle.
What is the significance of the house order (left to right)?: The linear order of the houses is critical. Rules involving relative positions like "immediately to the right of" (Rule #6) and "next to" (Rules #11, #12, #15) depend on a fixed ordering. In our code, this is represented by the index in the sequence, from 0 (the first house on the left) to 4 (the fifth house on the right).

Conclusion: From Logic Puzzle to Elegant Code

We began with a formidable logic puzzle, a challenge that has stumped thinkers for decades. By leveraging the principles of functional programming in Clojure, we transformed it into a clear, declarative, and efficient program. We saw how immutable data, lazy sequences, and powerful list comprehensions are not just abstract computer science concepts, but practical tools for solving complex problems with elegance.

The Zebra Puzzle is more than just a brain-teaser; it's a perfect case study for the power of constraint satisfaction programming and a testament to Clojure's fitness for this domain. The solution isn't a tangled mess of loops and state changes; it's a specification of the solution itself, letting the language and its abstractions do the heavy lifting.

Technology Disclaimer: The code in this article is written using idiomatic Clojure (1.11+) and standard library functions. It should be compatible with all modern Clojure versions. The concepts discussed are fundamental to the language.

Feeling inspired to tackle more computational challenges? Continue your journey by exploring the full kodikra Clojure Learning Path or deepen your understanding by consulting our complete guide to the Clojure language.

Published by Kodikra — Your trusted Clojure learning resource.

kodikra

Search this blog