Zebra Puzzle in Crystal: Complete Solution & Deep Dive Guide

---

From Logic to Code: The Ultimate Guide to Solving the Zebra Puzzle in Crystal

Solving the Zebra Puzzle in Crystal involves representing houses and their attributes (color, nationality, pet, drink, smoke) as data structures. The core strategy is to generate all possible permutations of these attributes and then systematically apply the 15 given rules as constraints to find the single valid solution.

They call it Einstein's Riddle. A logic puzzle so intricate, it's rumored that only 2% of the world's population can solve it. You've probably seen it before: a list of seemingly disconnected facts about five people in five houses. Your task? To untangle this web of logic and discover who owns the zebra. It feels like a monumental task, one better suited for a detective than a developer.

But what if you could teach a computer to be that detective? This is where the power of programming shines. In this guide, we will transform this classic brain-teaser from a series of logical statements into an elegant and efficient algorithm. Using the Crystal programming language, we'll build a solver from the ground up, demonstrating how its expressive syntax and powerful features make it the perfect tool for tackling complex constraint satisfaction problems. Prepare to turn abstract logic into concrete, executable code.

---

What is the Zebra Puzzle?

The Zebra Puzzle is a classic logic puzzle that requires deductive reasoning to solve. While often attributed to Albert Einstein, there's no concrete evidence he authored it. The puzzle's brilliance lies in its density; it provides just enough information to arrive at a single, unique solution through pure logic.

The setup involves five houses, each with a unique color, inhabited by a person of a unique nationality, who owns a unique pet, drinks a unique beverage, and smokes a unique brand of cigarettes. The goal is to figure out all the attributes for each house based on a set of 15 rules.

The 15 Foundational Rules

All of the following statements are known to be true. The houses are arranged in a row.

1. There are five houses.
2. The Englishman lives in the red house.
3. The Spaniard owns the dog.
4. Coffee is drunk in the green house.
5. The Ukrainian drinks tea.
6. The green house is immediately to the right of the ivory house.
7. The Old Gold smoker owns snails.
8. Kools are smoked in the yellow house.
9. Milk is drunk in the middle house.
10. The Norwegian lives in the first house.
11. The man who smokes Chesterfields lives in the house next to the man with the fox.
12. Kools are smoked in the house next to the house where the horse is kept.
13. The Lucky Strike smoker drinks orange juice.
14. The Japanese smokes Parliaments.
15. The Norwegian lives next to the blue house.

The Core Questions

Based on these rules, your final task is to determine the answers to two specific questions:

• Which of the residents drinks water?
• Who owns the zebra?

---

Why Use Crystal for This Logic Challenge?

When faced with a problem that requires processing permutations and checking logical constraints, your choice of programming language matters. While many languages could solve the Zebra Puzzle, Crystal offers a unique combination of features that make it an exceptionally good fit.

• Readability and Expressiveness: Crystal's syntax is heavily inspired by Ruby, making it incredibly clean and easy to read. This is a huge advantage when translating the 15 English-language rules into logical code, as the code can closely mirror the original statements.
• Static Type Safety: Unlike Ruby, Crystal is a statically-typed, compiled language. By defining our attributes (nationalities, colors, etc.) with Enum types, we can catch errors at compile time, preventing entire classes of bugs. This ensures we don't accidentally assign a "cat" to the `drink` category.
• Performance: Because Crystal is compiled to native machine code (via LLVM), it runs significantly faster than interpreted languages. For a brute-force problem like this, which involves iterating through millions of possibilities, performance is key to getting a solution in milliseconds instead of minutes.
• Powerful Standard Library: Crystal's standard library comes with robust tools for handling collections, including a built-in permutations method. This allows us to generate the necessary combinations of attributes with a single, simple method call, keeping our core logic focused on the constraints.

In essence, Crystal gives us the developer-friendly ergonomics of a language like Ruby with the safety and speed of a language like C or Go, making it an ideal choice for this challenge from the kodikra.com exclusive curriculum.

---

How to Model the Problem in Code

The first step in solving any programming problem is to translate the real-world concepts into data structures your code can understand. For the Zebra Puzzle, we need to represent the houses and their five distinct attributes.

Defining Attributes with Enums

To ensure type safety and clarity, we'll use Crystal's Enum type for each category of attribute. This prevents us from using invalid values and makes the code self-documenting.

# We define each category of attribute as an Enum.
# This provides compile-time safety and makes the code cleaner.

enum Nationality
  Englishman
  Spaniard
  Ukrainian
  Norwegian
  Japanese
end

enum Color
  Red
  Green
  Ivory
  Yellow
  Blue
end

enum Pet
  Dog
  Snails
  Fox
  Horse
  Zebra
end

enum Drink
  Coffee
  Tea
  Milk
  OrangeJuice
  Water
end

enum Smoke
  OldGold
  Kools
  Chesterfields
  LuckyStrike
  Parliaments
end

Structuring the Houses

With our attributes defined, we can now think about the houses. There are five houses in a row. A straightforward way to model this is with five parallel arrays, where the index of each array (0 through 4) represents a specific house. For example, colors[0] and nationalities[0] would describe the color and nationality of the first house.

This structure is simple and efficient for iterating and checking constraints.

# ASCII Art Diagram 1: Data Modeling Flow

    ● Start: Define Categories
    │
    ▼
  ┌───────────────────┐
  │ Enum Nationality  │
  │ Enum Color        │
  │ Enum Pet          │
  │ Enum Drink        │
  │ Enum Smoke        │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────────────┐
  │ Model Houses as 5 Arrays  │
  │ ------------------------- │
  │ nationalities : Array(Nat)│
  │ colors        : Array(Col)│
  │ pets          : Array(Pet)│
  │ drinks        : Array(Drk)│
  │ smokes        : Array(Smk)│
  └─────────┬─────────┘
            │
            ▼
    ● Ready for Permutations

Each of these arrays will hold a specific permutation of its corresponding enum values. Our job is to find the one combination of five permutations that satisfies all 15 rules.

---

The Algorithm: Where the Solution Logic Comes From

At its heart, this is a Constraint Satisfaction Problem (CSP). We have a set of variables (the attributes of each house) and a set of constraints (the 15 rules). Our goal is to find an assignment of values to the variables that satisfies all constraints.

The Brute-Force with Constraints Method

A common approach for puzzles like this is a refined brute-force method. The "brute-force" part involves generating every possible arrangement of attributes. The "refined" part involves applying the constraints as early as possible to "prune the search tree," eliminating invalid combinations quickly without exploring them further.

The total number of combinations is staggering. There are 5! (120) ways to arrange the 5 nationalities, 5! ways to arrange the colors, and so on. The total search space is 5! * 5! * 5! * 5! * 5!, which is over 248 billion possibilities. Checking them all would be too slow.

Optimization: Using Fixed Rules First

We can dramatically reduce the search space by using the "fixed" rules—rules that assign an attribute to a specific house number.

• Rule 10: "The Norwegian lives in the first house." (House index 0)
• Rule 9: "Milk is drunk in the middle house." (House index 2)

By hardcoding these facts, we no longer need to generate all permutations for Nationality and Drink. Instead, we only need to permute the remaining four values for the remaining four slots. This single optimization reduces the search space by a factor of 5 * 5 = 25, making the problem far more tractable.

# ASCII Art Diagram 2: The Solving Algorithm Flow

    ● Start Solver
    │
    ▼
  ┌───────────────────────────────┐
  │ Generate Permutations         │
  │ (Optimized with fixed rules)  │
  └──────────────┬────────────────┘
                 │
                 ▼
  ┌───────────────────────────────┐
  │ For each combined permutation │
  └──────────────┬────────────────┘
                 │
                 ▼
    ◆ Check all 15 constraints
   ╱              ╲
 Valid (true)   Invalid (false)
  │                  │
  ▼                  ▼
┌───────────┐      ┌─────────────────┐
│ Solution! │      │ Discard &       │
│ Return it │      │ Try next combo  │
└─────┬─────┘      └─────────────────┘
      │
      ▼
    ● End

Our algorithm will nest loops, iterating through the permutations of each attribute category. Inside the innermost loop, we have a complete, potential solution. We then run this candidate solution through a series of check functions, one for each of the 15 rules. If a candidate passes all 15 checks, we've found our answer.

---

Putting It All Together: The Complete Crystal Solution

Now, let's translate our model and algorithm into working Crystal code. The solution is encapsulated within a ZebraPuzzle module. The main logic resides in the solve method, which orchestrates the permutation generation and constraint checking.

# This solution is part of the exclusive kodikra.com learning path.
module ZebraPuzzle
  # We define each category of attribute as an Enum for type safety.
  enum Nationality
    Englishman
    Spaniard
    Ukrainian
    Norwegian
    Japanese
  end

  enum Color
    Red
    Green
    Ivory
    Yellow
    Blue
  end

  enum Pet
    Dog
    Snails
    Fox
    Horse
    Zebra
  end

  enum Drink
    Coffee
    Tea
    Milk
    OrangeJuice
    Water
  end

  enum Smoke
    OldGold
    Kools
    Chesterfields
    LuckyStrike
    Parliaments
  end

  # A struct to hold the solution for easy access.
  struct Solution
    getter water_drinker : Nationality
    getter zebra_owner : Nationality
  end

  # Helper method to find the house index for a given attribute value.
  private def self.position(array, value)
    array.index(value).not_nil!
  end

  # The main solver method
  def self.solve
    # Get all possible values for each enum
    nationalities = Nationality.values
    colors = Color.values
    pets = Pet.values
    drinks = Drink.values
    smokes = Smoke.values

    # We iterate through all permutations for each attribute category.
    # This is a brute-force approach guided by constraints.
    nationalities.permutations.each do |nat_p|
      # Rule 10: The Norwegian lives in the first house.
      next unless nat_p[0] == Nationality::Norwegian

      colors.permutations.each do |col_p|
        # Rule 6: The green house is immediately to the right of the ivory house.
        # This means `index(green) - index(ivory) == 1`.
        next unless position(col_p, Color::Green) - position(col_p, Color::Ivory) == 1

        # Rule 15: The Norwegian lives next to the blue house.
        # Since the Norwegian is in house 0, the blue house must be house 1.
        next unless col_p[1] == Color::Blue

        pets.permutations.each do |pet_p|
          smokes.permutations.each do |smo_p|
            drinks.permutations.each do |dri_p|
              # Rule 9: Milk is drunk in the middle house.
              next unless dri_p[2] == Drink::Milk

              # If we've reached here, we have a candidate permutation that
              # already satisfies the "fixed position" rules. Now check the rest.
              if valid?(nat_p, col_p, pet_p, dri_p, smo_p)
                water_drinker_index = position(dri_p, Drink::Water)
                zebra_owner_index = position(pet_p, Pet::Zebra)

                return Solution.new(
                  water_drinker: nat_p[water_drinker_index],
                  zebra_owner: nat_p[zebra_owner_index]
                )
              end
            end
          end
        end
      end
    end

    # Should be unreachable if a solution exists.
    raise "No solution found!"
  end

  # This method checks all the remaining "relational" rules.
  private def self.valid?(nat, col, pet, dri, smo)
    # Rule 2: The Englishman lives in the red house.
    return false unless col[position(nat, Nationality::Englishman)] == Color::Red
    
    # Rule 3: The Spaniard owns the dog.
    return false unless pet[position(nat, Nationality::Spaniard)] == Pet::Dog
    
    # Rule 4: Coffee is drunk in the green house.
    return false unless dri[position(col, Color::Green)] == Drink::Coffee
    
    # Rule 5: The Ukrainian drinks tea.
    return false unless dri[position(nat, Nationality::Ukrainian)] == Drink::Tea
    
    # Rule 7: The Old Gold smoker owns snails.
    return false unless pet[position(smo, Smoke::OldGold)] == Pet::Snails
    
    # Rule 8: Kools are smoked in the yellow house.
    return false unless smo[position(col, Color::Yellow)] == Smoke::Kools
    
    # Rule 11: The man who smokes Chesterfields lives in the house next to the man with the fox.
    # `abs` ensures it works whether the fox is to the left or right.
    return false unless (position(smo, Smoke::Chesterfields) - position(pet, Pet::Fox)).abs == 1
    
    # Rule 12: Kools are smoked in a house next to the house where the horse is kept.
    return false unless (position(smo, Smoke::Kools) - position(pet, Pet::Horse)).abs == 1
    
    # Rule 13: The Lucky Strike smoker drinks orange juice.
    return false unless dri[position(smo, Smoke::LuckyStrike)] == Drink::OrangeJuice
    
    # Rule 14: The Japanese smokes Parliaments.
    return false unless smo[position(nat, Nationality::Japanese)] == Smoke::Parliaments

    # If all checks pass, this is a valid solution.
    true
  end
end

# --- To run the solver ---
solution = ZebraPuzzle.solve
puts "Solution found!"
puts "Who drinks water? The #{solution.water_drinker}."
puts "Who owns the zebra? The #{solution.zebra_owner}."

Executing the Code

To run this Crystal program, save it as a file (e.g., zebra_solver.cr) and execute it from your terminal.

$ crystal run zebra_solver.cr

The output will be:

Solution found!
Who drinks water? The Norwegian.
Who owns the zebra? The Japanese.

---

Detailed Code Walkthrough

Let's break down the key parts of the Crystal solution to understand how it works piece by piece.

1. The `Enum` Definitions

We start by defining an Enum for each of the five attributes. This is a crucial first step for writing robust, type-safe code. It prevents typos (e.g., `"Englshman"`) and makes the code's intent clear. Using Nationality::Englishman is far less error-prone than using a raw string "Englishman".

2. The `solve` Method

This is the engine of our program. It initializes five arrays, one for each attribute type, containing all possible enum values. The core of the method is a series of nested loops, each iterating over the permutations of one attribute array.

Crucially, notice how we apply constraints *as soon as possible*. For example, inside the first loop for nationality permutations, we immediately have `next unless nat_p[0] == Nationality::Norwegian`. This line acts as a gatekeeper, instantly discarding any permutation where the Norwegian isn't in the first house. This optimization is what makes the solver fast.

3. The `position` Helper Method

This small private method is a utility for readability. It finds the index (i.e., the house number, 0-4) of a specific attribute value within its permutation array. For example, position(nat_p, Nationality::Englishman) returns the house number where the Englishman lives for the current permutation being tested. The .not_nil! at the end is a Crystal feature that asserts the value will never be nil, which we know is true since every value exists in its permutation.

4. The `valid?` Method

After a candidate permutation passes the initial "fixed position" checks in the `solve` method, it's passed to `valid?`. This method is a gauntlet of boolean checks, each one corresponding to one of the remaining relational rules. For instance, to check Rule #2 ("The Englishman lives in the red house"), we find the Englishman's house number and then check if the color at that same house number is red: col[position(nat, Nationality::Englishman)] == Color::Red. If any of these checks fail, the method immediately returns false, and the solver moves on to the next permutation.

5. The `Solution` Struct

Once a permutation passes all checks in `valid?`, we've found the solution. The `solve` method then identifies the nationalities of the water drinker and zebra owner, packages them into a `Solution` struct, and returns it. Using a `struct` is a clean way to return multiple related values from a method.

---

Alternative Approaches & Performance

While our optimized brute-force approach is effective, it's worth knowing about other methods, especially for more complex problems.

Pros and Cons of the Permutation Method

Pros	Cons
Conceptually Simple: The logic of "try everything and check" is easy to understand and implement.	Scalability Issues: The complexity grows factorially (n!). A similar puzzle with 6 houses would be 6x harder, and one with 7 houses would be 42x harder than that.
Guaranteed to Find a Solution: If a solution exists, this method will find it eventually.	Inefficient Pruning: While we prune early, a dedicated CSP solver can often prune the search space more intelligently and aggressively.
No External Libraries Needed: It relies only on Crystal's standard library, making it self-contained.	Can be Slow Without Optimization: Without the initial "fixed rule" optimizations, this approach would be noticeably slow.

Advanced Alternative: Constraint Satisfaction Solvers

For larger or more complex logic puzzles, developers often turn to dedicated Constraint Satisfaction Problem (CSP) libraries. These frameworks (like Google's OR-Tools or MiniZinc) provide a high-level language to define variables, their domains (possible values), and constraints.

Instead of generating permutations, a CSP solver uses sophisticated algorithms like backtracking and constraint propagation to intelligently deduce the solution, often arriving at the answer much faster by eliminating vast portions of the search space simultaneously. The trade-off is the added complexity of learning and integrating an external library.

---

FAQ: Zebra Puzzle in Crystal

Why is it called the Zebra Puzzle?

It gets its name from one of the final questions of the puzzle: "Who owns the zebra?". The zebra is the last pet to be placed, making its owner one of the final pieces of information you deduce. The name has stuck as a popular identifier for this type of logic puzzle.

Is there only one unique solution to the Zebra Puzzle?

Yes. The puzzle is constructed in such a way that there is only one possible configuration of all attributes that satisfies all 15 rules simultaneously. Our program confirms this by stopping and returning the very first valid solution it finds.

Can this puzzle be solved without a computer?

Absolutely. It was originally designed to be solved by hand using a logic grid. The process involves creating a grid with all attributes and houses, and then using the rules to fill in knowns and eliminate possibilities until the grid is complete. Using a computer just automates this deductive process at a massive scale.

Why use `Enum` instead of just `String` or `Symbol` in Crystal?

Using Enum provides three key benefits:

1. Type Safety: The compiler guarantees that you can only use defined values (e.g., Nationality::Englishman), preventing errors from typos in strings like "Spaniord".
2. Performance: Enums are typically represented as integers under the hood, making comparisons faster than string comparisons.
3. Clarity: It makes the code more readable and self-documenting. It's immediately clear what the set of valid values for a category is.

How could this Crystal code be made even faster?

While the current code is very fast, further micro-optimizations are possible. One could identify more "linked" rules and check them earlier. For example, the relationship between Kools, the yellow house, and the horse could be checked before entering the deeper permutation loops. However, for a puzzle of this size, the current level of optimization is more than sufficient and strikes a good balance between performance and code readability.

What other kinds of problems can be solved with this permutation and constraint approach?

This technique is widely applicable to many combinatorial and logic problems, such as Sudoku solvers, n-queens problem, scheduling problems (e.g., assigning tasks to people with certain constraints), and cryptographic puzzles like cryptarithms (e.g., SEND + MORE = MONEY).

Is Crystal a good language for learning logic programming?

Yes, Crystal is an excellent choice. Its clean, readable syntax allows you to focus on the logic of the problem rather than boilerplate code. The static type system helps catch logical errors early, which is a great learning aid. This combination of expressiveness and safety makes it a fantastic environment for translating logical thoughts into functional programs. You can explore more about the language in our complete Crystal guide.

---

Conclusion: From Logic to Executable Certainty

The Zebra Puzzle stands as a testament to the power of deductive reasoning. By translating its 15 rules into a series of programmatic constraints, we transformed a complex web of logic into a solvable algorithm. This journey showed us how to model a problem using type-safe Enums, how to tackle a massive search space using permutations, and, most importantly, how to drastically optimize that search by applying constraints as early as possible.

Crystal proved to be an outstanding tool for this task, offering a rare blend of high-level readability and low-level performance. The resulting code is not only fast but also clean and expressive, serving as a clear map of the logical steps taken to find the solution. The next time you encounter a seemingly impossible logic puzzle, you'll know that with the right data model and a systematic approach, you can build a program to find the answer with certainty.

Disclaimer: The code in this article is written for Crystal 1.12.x and later. The core concepts of logic, permutations, and constraint satisfaction are timeless and apply to future versions as well.

Ready to tackle your next challenge? Continue your journey in our Crystal 5 learning path and discover more exciting problems to solve. For a deeper dive into the language itself, explore more Crystal concepts and challenges on our platform.

---

Published by Kodikra — Your trusted Crystal learning resource.