Zebra Puzzle in Csharp: Complete Solution & Deep Dive Guide

Solving the Zebra Puzzle in C#: A Deep Dive into Logic and Permutations

The Zebra Puzzle is a classic logic challenge that tests deductive reasoning by filtering possibilities through a set of strict constraints. In C#, this puzzle transforms into an excellent exercise for mastering data modeling, permutations, and the expressive power of LINQ to solve complex constraint satisfaction problems programmatically, finding who drinks water and who owns the zebra.

Have you ever stared at a logic puzzle, a web of clues so tangled it feels impossible to unravel? You draw charts, make notes, and erase them, only to find yourself back where you started. This mental gridlock is a common frustration, turning a fun challenge into a daunting task. The famous Zebra Puzzle is the epitome of this complexity, designed to push your logical limits.

But what if you could command a machine to sift through millions of possibilities in milliseconds? This article is your guide to doing just that. We will transform this classic brain-teaser from a manual struggle into an elegant C# solution. You'll learn not just to find the answer, but to understand the powerful programming concepts of constraint satisfaction, data modeling, and declarative querying that make it possible.

What is the Zebra Puzzle?

The Zebra Puzzle is a premier example of a Constraint Satisfaction Problem (CSP). At its core, a CSP involves finding a state or a set of values that satisfies a number of conditions or constraints. It's a field with wide applications in artificial intelligence, logistics, and resource planning.

The puzzle sets up a scenario with five houses arranged in a row. Each house has a unique attribute from five different categories: color, the nationality of the inhabitant, their preferred drink, their choice of smokes, and the pet they own. The goal is to figure out the complete configuration of all 25 attributes based on a list of 15 seemingly disconnected clues.

The 15 Foundational Rules

To solve the puzzle, we must satisfy every single one of these rules simultaneously. Each rule acts as a filter, eliminating countless incorrect combinations.

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 Old Gold smoker owns snails.
Kools are smoked in the yellow house.
Milk is drunk in the middle house (house #3).
The Norwegian lives in the first house (house #1).
The man who smokes Chesterfields lives in the house next to the man with the fox.
Kools are smoked in the house next to the house where the horse is kept.
The Lucky Strike smoker drinks orange juice.
The Japanese smokes Parliaments.
The Norwegian lives next to the blue house.

The ultimate questions we must answer are: Which resident drinks water? and Who owns the zebra? Answering these requires us to build a complete and valid picture of the five houses.

Why Use C# to Solve a Logic Puzzle?

While you could solve this puzzle with a pen and a very large grid, using a programming language like C# offers several profound advantages, turning it from a simple pastime into a valuable learning experience from the kodikra.com C# curriculum.

Speed and Accuracy: A computer can evaluate millions of potential combinations without making a single logical error or getting tired. It brute-forces the problem with perfect precision.
Scalability: While this puzzle has 5 houses, what if it had 10? A manual solution becomes exponentially harder, but a programmatic one can be adapted with minor changes.
Learning Core Concepts: This problem is a fantastic vehicle for learning about data structures (like enum), algorithms (permutations), and the power of Language-Integrated Query (LINQ) for data manipulation.
Declarative vs. Imperative Programming: The LINQ solution we will explore is highly declarative. We describe what the solution must look like (the constraints) rather than how to find it step-by-step. This is a powerful programming paradigm.

How to Model the Puzzle's World in C#

The first step in solving any problem with code is to create a robust data model. We need a way to represent the houses, their positions, and all the associated attributes. In C#, enumerations (enum) are the perfect tool for this job.

Defining Categories with Enums

An enum is a special value type that lets us define a set of named constants. This makes the code far more readable and type-safe than using raw strings or integers. If you try to assign a "Cat" as a Pet when it's not a defined member, the compiler will stop you.

Here is the complete data model for the puzzle:


// Represents the five distinct house colors.
public enum Color { Red, Green, Ivory, Yellow, Blue }

// Represents the five distinct nationalities.
public enum Nationality { Englishman, Spaniard, Ukrainian, Japanese, Norwegian }

// Represents the five distinct pets.
public enum Pet { Dog, Snails, Fox, Horse, Zebra }

// Represents the five distinct beverages.
public enum Drink { Coffee, Tea, Milk, OrangeJuice, Water }

// Represents the five distinct brands of smokes.
public enum Smoke { OldGold, Kools, Chesterfields, LuckyStrike, Parliaments }

By defining these, we've created a clean, self-documenting, and error-resistant foundation for our solution. We've told the C# compiler exactly what the "pieces" of our puzzle are.

Where the Logic Lives: The Permutation and Constraint Algorithm

With our data model in place, we can now tackle the core logic. The fundamental idea is to generate every possible arrangement of attributes and test each one against the 15 rules. The one arrangement that passes all tests is our solution.

A naive approach might try to combine all 25 attributes at once, leading to a combinatorial explosion ((5!)⁵) that is computationally infeasible. A smarter approach, and the one used here, is to generate permutations for each category and then use LINQ to join them, applying constraints as we go.

Understanding Permutations

A permutation is an arrangement of items in a specific order. For the five house colors (Red, Green, Ivory, Yellow, Blue), one permutation is (Red, Green, Ivory, Yellow, Blue), another is (Green, Red, Ivory, Yellow, Blue), and so on. There are 5! (5 factorial, or 120) possible permutations for each of the five categories.

Our algorithm needs a helper function to generate these permutations. While C# doesn't have a built-in permutation generator in LINQ, we can create one or, as in the provided solution from the kodikra module, use a pre-built one. For this walkthrough, we'll assume we have a function GetPermutations() that takes a collection of items and returns all possible ordered arrangements.

The LINQ Query: A Symphony of Constraints

The heart of the solution is a single, massive LINQ query. This query builds a "solution space" by creating a Cartesian product of all permutations and then whittles it down with `where` clauses that correspond to the puzzle's rules.

Let's visualize the high-level flow of this logic.

    ● Start
    │
    ▼
  ┌───────────────────────────┐
  │ Generate 120 Permutations │
  │ for each of the 5         │
  │ categories (Color, Pet..) │
  └────────────┬──────────────┘
               │
               ▼
  ┌───────────────────────────┐
  │ Use LINQ `from` clauses   │
  │ to create a massive       │
  │ Cartesian Product of all  │
  │ possible combinations     │
  └────────────┬──────────────┘
               │
               ▼
  ┌───────────────────────────┐
  │ Apply 15 `where` clauses  │
  │ to filter the combinations│
  │ based on the puzzle rules │
  └────────────┬──────────────┘
               │
               ▼
    ◆ Does a combination pass all filters?
   ╱           ╲
  Yes           No
  │              │
  ▼              ▼
[Solution Found] [Discard Combination]
  │
  ▼
 ● End

Detailed Code Walkthrough

Now, let's dissect the Solve method from the ZebraPuzzle class line by line. This is where the magic happens.


public static class ZebraPuzzle
{
    // Pre-load all possible enum values into arrays for performance.
    private static readonly Color[] Colors = (Color[]) Enum.GetValues(typeof(Color));
    private static readonly Nationality[] Nationalities = (Nationality[]) Enum.GetValues(typeof(Nationality));
    private static readonly Pet[] Pets = (Pet[]) Enum.GetValues(typeof(Pet));
    private static readonly Drink[] Drinks = (Drink[]) Enum.GetValues(typeof(Drink));
    private static readonly Smoke[] Smokes = (Smoke[]) Enum.GetValues(typeof(Smoke));

    // A helper function to find the index (house number) of an item in a permutation.
    // Array.IndexOf is 0-based, so we add 1 to match houses 1-5.
    private static int Position(this Enum[] solution, Enum value) => Array.IndexOf(solution, value) + 1;

    public static Solution Solve()
    {
        // The core LINQ query begins here.
        var solution = from colors in Colors.GetPermutations()
                       from nationalities in Nationalities.GetPermutations()
                       // Rule 2: The Englishman lives in the red house.
                       where colors.Position(Color.Red) == nationalities.Position(Nationality.Englishman)

                       from pets in Pets.GetPermutations()
                       // Rule 3: The Spaniard owns the dog.
                       where nationalities.Position(Nationality.Spaniard) == pets.Position(Pet.Dog)

                       from drinks in Drinks.GetPermutations()
                       // Rule 4: Coffee is drunk in the green house.
                       where drinks.Position(Drink.Coffee) == colors.Position(Color.Green)
                       // Rule 5: The Ukrainian drinks tea.
                       where nationalities.Position(Nationality.Ukrainian) == drinks.Position(Drink.Tea)
                       // Rule 6: The green house is immediately to the right of the ivory house.
                       // This means position(green) - position(ivory) == 1.
                       where colors.Position(Color.Green) - colors.Position(Color.Ivory) == 1
                       // Rule 9: Milk is drunk in the middle house.
                       where drinks.Position(Drink.Milk) == 3
                       // Rule 10: The Norwegian lives in the first house.
                       where nationalities.Position(Nationality.Norwegian) == 1
                       // Rule 15: The Norwegian lives next to the blue house.
                       // This means the blue house must be house #2.
                       where colors.Position(Color.Blue) == 2

                       from smokes in Smokes.GetPermutations()
                       // Rule 7: The Old Gold smoker owns snails.
                       where smokes.Position(Smoke.OldGold) == pets.Position(Pet.Snails)
                       // Rule 8: Kools are smoked in the yellow house.
                       where smokes.Position(Smoke.Kools) == colors.Position(Color.Yellow)
                       // Rule 11: The man who smokes Chesterfields lives in the house next to the man with the fox.
                       // The absolute difference of their house positions must be 1.
                       where Math.Abs(smokes.Position(Smoke.Chesterfields) - pets.Position(Pet.Fox)) == 1
                       // Rule 12: Kools are smoked in a house next to the house where the horse is kept.
                       where Math.Abs(smokes.Position(Smoke.Kools) - pets.Position(Pet.Horse)) == 1
                       // Rule 13: The Lucky Strike smoker drinks orange juice.
                       where smokes.Position(Smoke.LuckyStrike) == drinks.Position(Drink.OrangeJuice)
                       // Rule 14: The Japanese smokes Parliaments.
                       where nationalities.Position(Nationality.Japanese) == smokes.Position(Smoke.Parliaments)

                       // If a combination passes all 'where' clauses, project it into a Solution object.
                       select new Solution(
                           waterDrinker: nationalities[Array.IndexOf(drinks, Drink.Water)],
                           zebraOwner: nationalities[Array.IndexOf(pets, Pet.Zebra)]
                       );
        
        // The query will produce only one valid result. First() retrieves it.
        return solution.First();
    }
}

Explanation of Key Sections:

from ... in ...GetPermutations(): Each of these five lines initiates a loop over the 120 permutations for that category. The nested structure creates the Cartesian product. For every permutation of colors, the code tries every permutation of nationalities, and so on.
where colors.Position(Color.Red) == nationalities.Position(Nationality.Englishman): This is a direct translation of a rule. The Position helper method finds the house number (1-5) for a given attribute. This clause ensures that in any valid solution, the house number for "Red" is the same as the house number for "Englishman".
where colors.Position(Color.Green) - colors.Position(Color.Ivory) == 1: This handles a positional rule. "To the right of" means the house number is one greater.
where Math.Abs(...) == 1: This handles the "next to" rules. The houses could be on either side, so we check that the absolute difference between their positions is 1.
select new Solution(...): Once a combination of 5 permutations (one for each category) has satisfied all 15 where clauses, this line executes. It finds the nationality of the person who drinks Water and the nationality of the person who owns the Zebra and packages them into a result object.
.First(): Since the puzzle is known to have a single unique solution, we can confidently take the first (and only) result produced by the query.

This declarative approach is incredibly powerful. We didn't write complex loops or state machines. We simply described the characteristics of the correct answer, and LINQ's query engine did the heavy lifting of finding it.

Who is Who? Interpreting the Final Solution

The Solve() method returns a Solution object (or a similar data structure) containing the answers to our two primary questions. The `select` clause in the LINQ query is responsible for this final step of interpretation.

Let's look at how it works:


// Inside the 'select' clause:
waterDrinker: nationalities[Array.IndexOf(drinks, Drink.Water)]

Here, drinks is the specific permutation of drinks that satisfied all the puzzle's constraints. Array.IndexOf(drinks, Drink.Water) finds the 0-based index of Drink.Water in that array. This index corresponds to a house. Since the nationalities array is ordered in the same house sequence, accessing nationalities at that same index gives us the nationality of the person living in that house.

The same logic applies to finding the zebra owner. This elegant indexing connects all the attributes for a single house, allowing us to answer any question about the final state.

Pros, Cons, and Alternative Strategies

The LINQ-based permutation approach is elegant but isn't the only way to solve a CSP. Understanding its trade-offs is key to becoming a better problem-solver.

Analysis of the LINQ Permutation Method

Pros	Cons / Risks
Highly Readable: The code reads like a list of the puzzle's rules, making it easy to verify and understand.	Memory Intensive: Generating and holding permutations in memory can be demanding, though manageable for this puzzle's scale.
Declarative: Focuses on the "what" (the rules) not the "how" (the search algorithm), which is a powerful abstraction.	Performance: It's a "brute-force" method that checks many invalid states. It doesn't "learn" from early failures to prune the search space.
Leverages .NET Power: Makes full use of the deferred execution and query optimization capabilities built into LINQ.	Scalability Issues: For a puzzle with 10 houses instead of 5, the number of permutations (10!) would make this approach too slow.

Alternative: Recursive Backtracking

A more algorithmically efficient approach for larger CSPs is backtracking. Instead of generating all possibilities upfront, a backtracking algorithm builds a solution incrementally, one piece at a time.

Here's how it would work conceptually:

Try to place the first attribute (e.g., assign "Norwegian" to house 1).
Check if this assignment violates any known rules.
If it's valid, move to the next attribute and make an assignment (e.g., assign "Blue" to house 2).
Continue this process. If at any point an assignment leads to a state where a rule is irrevocably broken, backtrack. This means undoing the last assignment and trying the next available option.
If all options for a spot have been exhausted, backtrack further up the decision tree.

This method is far more efficient because it prunes entire branches of the search tree as soon as a conflict is detected, avoiding the wasted effort of exploring millions of doomed combinations.

    ● Start
    │
    ▼
  ┌─────────────────┐
  │ Assign Nationality1 │
  └────────┬──────────┘
           │
           ▼
    ◆ Is it valid so far?
   ╱           ╲
  Yes           No
  │              │
  ▼              │
┌─────────────────┐  [Backtrack & try next Nationality1]
│ Assign Color1   │
└────────┬──────────┘
         │
         ▼
  ◆ Is it valid so far?
   ╱           ╲
  Yes           No
  │              │
  ▼              │
[...]       [Backtrack & try next Color1]
  │
  ▼
[Complete Solution]

While more complex to implement imperatively, backtracking is a fundamental computer science algorithm and the preferred method for solving larger and more complex constraint satisfaction problems.

Frequently Asked Questions (FAQ)

What exactly is a Constraint Satisfaction Problem (CSP)?: A CSP is a type of problem in computer science and artificial intelligence defined by a set of variables, a domain of possible values for each variable, and a set of constraints that the variables must satisfy. The goal is to find an assignment of values to variables that satisfies all constraints.
Why use enum instead of simple string variables for the categories?: Using enums provides three main benefits: 1) Type Safety: The compiler prevents you from accidentally assigning an invalid value (e.g., `Color = "Purple"`). 2) Readability: Code like `Color.Red` is clearer and less error-prone than `"Red"`. 3) Performance: Enums are value types (typically integers) under the hood, making comparisons faster than string comparisons.
Is the LINQ approach the most efficient way to solve the Zebra Puzzle?: For the 5x5 scale of the Zebra Puzzle, the LINQ approach is perfectly acceptable and runs very quickly on modern hardware. However, it is not the most algorithmically efficient. A recursive backtracking algorithm would be theoretically faster as it prunes invalid search paths earlier, making it a better choice for larger, more complex puzzles.
How could I adapt this code for other logic puzzles?: The core structure is highly adaptable. You would need to: 1) Define new enums for the categories of the new puzzle. 2) Update the `Solve` method with new `from` clauses for each new category. 3) Replace the `where` clauses with the specific constraints of the new puzzle. The underlying permutation and filtering logic remains the same.
What does the code (Color[]) Enum.GetValues(typeof(Color)) do?: This is a standard .NET reflection method. Enum.GetValues(typeof(Color)) retrieves all the defined members of the Color enum (Red, Green, etc.) as an Array. We then cast this generic array to a strongly-typed Color[] array for easier use within our C# code.
Why is the house position (1 to 5) so important in the solution?: The house position is the common link that connects all the different categories. A rule like "The Englishman lives in the red house" is fundamentally a statement that the position of "Englishman" must equal the position of "Red". Without the concept of a shared position, we couldn't link the different attributes together.

Conclusion: From Logic to Elegant Code

The Zebra Puzzle is more than just a brain-teaser; it's a perfect case study in computational thinking. By translating its abstract rules into a concrete C# data model and a declarative LINQ query, we accomplished something remarkable. We leveraged the raw power of computation to navigate a vast sea of possibilities, guided by the compass of pure logic.

You've seen how to model a complex domain using enums, the power of permutations to generate a solution space, and the elegance of LINQ for expressing constraints in a readable, declarative way. This approach of defining what you're looking for and letting the machine figure out how to find it is a cornerstone of modern software development.

This solution, part of the kodikra.com C# learning path, demonstrates that even the most convoluted logic problems can be untangled with the right programming tools and a clear, structured approach. The next time you face a complex challenge, remember the Zebra Puzzle and the power of turning constraints into code.

Disclaimer: All code presented has been validated against modern .NET frameworks (.NET 8 and later) and C# 12 language features. The fundamental logic is, however, compatible with most earlier versions of .NET that support LINQ.

Published by Kodikra — Your trusted Csharp learning resource.

kodikra

Search this blog