Zebra Puzzle in C: Complete Solution & Deep Dive Guide
Cracking the Zebra Puzzle in C: A Step-by-Step Algorithmic Approach
Solving the Zebra Puzzle in C involves representing houses, nationalities, pets, drinks, and hobbies as enumerated types. The solution uses a brute-force permutation algorithm to systematically test every possible arrangement against the 15 puzzle rules until a valid configuration is found, revealing who drinks water and who owns the zebra.
You stare at a list of seemingly disconnected facts: an Englishman in a red house, a Spaniard who owns a dog, someone drinking coffee in a green house. It feels like a tangled web of information with no clear starting point. This is the classic Zebra Puzzle, a logic problem so renowned it's often, though perhaps apocryphally, attributed to a young Albert Einstein.
Many of us have tried to solve it with pen and paper, creating complex grids that quickly become a mess. But what if we could teach a machine to untangle this web for us? What if we could translate this intricate logic into the precise, unforgiving syntax of the C programming language?
This guide promises to do just that. We will take you from the confusing maze of 15 rules to a clean, functional, and efficient C program that solves the puzzle algorithmically. You will not only find the answer but also gain a deep understanding of how to model and solve complex constraint satisfaction problems using brute-force permutation—a powerful tool in any programmer's arsenal.
What is the Zebra Puzzle?
The Zebra Puzzle is a quintessential logic puzzle that requires strong deductive reasoning. It falls into a category of problems known as constraint satisfaction problems (CSPs), where the goal is to find a state or configuration that satisfies a number of given conditions or constraints.
The setup involves five houses, arranged in a row. Each house has a unique attribute from five different categories: color, nationality of the resident, their preferred beverage, their pet, and their hobby. The challenge is that you are not given the direct relationships, but rather a set of 15 rules that connect these attributes.
The 15 Foundational Rules
To solve the puzzle, we must find a configuration of the five houses that simultaneously satisfies all of the following statements:
- 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 snail owner is a stamp collector.
- The diplomat lives in the yellow house.
- Milk is drunk in the middle house (house #3).
- The Norwegian lives in the first house (house #1).
- The doctor lives next to the fox owner.
- The diplomat lives next to the horse owner.
- The violinist drinks orange juice.
- The Japanese is a painter.
- The Norwegian lives next to the blue house.
The Core Questions
After processing all 15 rules and determining the exact configuration of all five houses, the final objective is to answer two specific questions:
- Which resident drinks water?
- Who owns the zebra?
The beauty of the puzzle is that these two pieces of information are not explicitly stated in the rules. They are emergent facts that can only be discovered once the entire logical grid has been correctly assembled.
Why Use C for this Logic Puzzle?
While a modern language like Python or JavaScript could solve this puzzle with more concise syntax, choosing C offers a unique and valuable learning experience. C forces you to engage with the problem at a lower level, providing deeper insight into memory management, performance, and algorithmic implementation.
Performance and Control
C is renowned for its speed. For a problem like the Zebra Puzzle, which we will solve using a brute-force approach that tests millions of possibilities, performance is key. C's direct memory manipulation and compilation to highly optimized machine code mean our permutation-generating engine will run exceptionally fast.
Algorithmic Transparency
In higher-level languages, a function to generate permutations might be available in a standard library, hiding the complex logic from the developer. In C, we often build these algorithms from scratch. This guide will walk you through implementing a next_permutation function, giving you a fundamental understanding of how these powerful algorithms work under the hood.
A Foundational Learning Tool
Solving this puzzle in C reinforces core programming concepts like enumerations (enum), pointers, arrays, and complex conditional logic. It's a perfect exercise from the kodikra learning path that bridges the gap between basic syntax and advanced problem-solving, making you a more disciplined and capable programmer.
How to Implement the Zebra Puzzle Solver in C
Our strategy is to use a systematic brute-force search. Since there are 5 houses and 5 attributes for each category, we can represent each category as a permutation of the numbers 0 through 4. We will generate every possible combination of these permutations and test each one against the 15 rules. The first combination that satisfies all rules is our solution.
The Overall Logic Flow
The program's high-level logic can be visualized as a pipeline. We generate a possible arrangement, test it, and if it fails, we generate the next one until a solution is found.
● Start
│
▼
┌───────────────────────────┐
│ Define Categories via Enums │
│ (Color, Nationality, etc.) │
└────────────┬──────────────┘
│
▼
┌───────────────────────────┐
│ Generate Permutations for │
│ All 5 Categories │
└────────────┬──────────────┘
│
▼
◆ Does this combination
satisfy all 15 rules? ◆
╱ ╲
Yes No
│ │
▼ ▼
┌──────────────┐ ┌───────────────────┐
│ Solution Found │ │ Generate Next │
│ Print & Exit │ │ Permutation & Repeat│
└──────────────┘ └───────────────────┘
│
▼
● End
Part 1: Defining the Data Structures (`zebra_puzzle.h`)
Before we write the logic, we must model the puzzle's entities. Using enums is the perfect way to do this in C. It makes the code self-documenting and prevents errors from using raw numbers or strings. Each item in a category is assigned a unique integer value, which we can use as an index.
#ifndef ZEBRA_PUZZLE_H
#define ZEBRA_PUZZLE_H
// Represents the solution structure
typedef struct {
const char *water_drinker;
const char *zebra_owner;
} solution_t;
// Function prototype for the solver
solution_t solve_puzzle(void);
// Enums for each category to make the code readable
// The order here is arbitrary but must be consistent.
enum Nationality { ENGLISHMAN, SPANIARD, UKRAINIAN, NORWEGIAN, JAPANESE };
enum Color { RED, GREEN, IVORY, YELLOW, BLUE };
enum Pet { DOG, SNAILS, FOX, HORSE, ZEBRA };
enum Beverage { COFFEE, TEA, MILK, ORANGE_JUICE, WATER };
enum Hobby { STAMPS, DIPLOMAT, VIOLINIST, PAINTER, DOCTOR };
#endif
In this header file, we define our five categories. We also declare the solution_t struct, which will hold the final answers, and the prototype for our main solver function, solve_puzzle.
Part 2: The Core Solver Logic (`zebra_puzzle.c`)
This is where the main algorithm resides. We will break down the implementation into three key parts: the permutation generator, the main solver loop, and the rule-checking logic.
The Permutation Engine: `next_permutation`
To test every possibility, we need a function that can take an ordered list (like {0, 1, 2, 3, 4}) and transform it into the next lexicographically larger arrangement (e.g., from {0, 1, 2, 4, 3} to {0, 1, 3, 2, 4}). This is a classic algorithm.
The logic follows these steps:
- Find the largest index
ksuch thata[k] < a[k + 1]. If no such index exists, the permutation is the last permutation. - Find the largest index
l > ksuch thata[k] < a[l]. - Swap the value of
a[k]with that ofa[l]. - Reverse the sequence from
a[k + 1]up to and including the final element.
● Start with a permutation (e.g., [0, 3, 4, 2, 1])
│
▼
┌───────────────────────────┐
│ 1. Find Pivot (k) │
│ (Largest k where a[k] < a[k+1]) │
│ [0, 3, 4, 2, 1] -> k=0 (a[0]=0 < a[1]=3)
└────────────┬──────────────┘
│
▼
┌───────────────────────────┐
│ 2. Find Successor (l) │
│ (Largest l > k where a[k] < a[l]) │
│ [0, 3, 4, 2, 1] -> l=1 (a[0]=0 < a[1]=3)
└────────────┬──────────────┘
│
▼
┌───────────────────────────┐
│ 3. Swap Pivot & Successor │
│ swap(a[k], a[l]) │
│ [3, 0, 4, 2, 1]
└────────────┬──────────────┘
│
▼
┌───────────────────────────┐
│ 4. Reverse Suffix │
│ (Reverse from k+1 to end) │
│ [3, 1, 2, 4, 0]
└────────────┬──────────────┘
│
▼
● End with next permutation
Here is the C implementation of this logic. The swap helper function is a simple utility for exchanging two integer values.
#include "zebra_puzzle.h"
#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
enum { NUM_HOUSES = 5 };
// Helper to swap two integer pointers
static inline void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
// Generates the next lexicographical permutation of an array
static bool next_permutation(int order[NUM_HOUSES]) {
// Step 1: Find the pivot
int k = -1;
for (int i = 0; i < NUM_HOUSES - 1; i++) {
if (order[i] < order[i + 1]) {
k = i;
}
}
if (k == -1) {
return false; // This was the last permutation
}
// Step 2: Find the successor
int l = -1;
for (int i = k + 1; i < NUM_HOUSES; i++) {
if (order[k] < order[i]) {
l = i;
}
}
// Step 3: Swap pivot and successor
swap(&order[k], &order[l]);
// Step 4: Reverse the suffix
int start = k + 1;
int end = NUM_HOUSES - 1;
while (start < end) {
swap(&order[start], &order[end]);
start++;
end--;
}
return true;
}
The Main Solver: `solve_puzzle`
The solver function initializes five arrays, one for each category, with the values {0, 1, 2, 3, 4}. It then enters a deeply nested set of loops. The outer loop generates permutations for nationalities, and for each nationality permutation, the next inner loop generates all permutations for colors, and so on.
This creates a massive search space. Since there are 5! (120) permutations for each of the 5 categories, the total number of combinations to check is 120^5, which is almost 2.5 billion. However, we can optimize this significantly. We can apply some rules *before* entering the deepest loops. For example, we know the Englishman lives in the red house. We can check this rule early and skip billions of invalid combinations.
The provided solution from the kodikra.com module takes a slightly different, more straightforward approach. It generates all permutations first and then checks all rules inside the innermost loop. While less optimized, it's easier to read and understand. Let's walk through that implementation.
solution_t solve_puzzle(void) {
// Arrays to hold the permutation for each category
int nationality[NUM_HOUSES] = {0, 1, 2, 3, 4};
int color[NUM_HOUSES] = {0, 1, 2, 3, 4};
int pet[NUM_HOUSES] = {0, 1, 2, 3, 4};
int beverage[NUM_HOUSES] = {0, 1, 2, 3, 4};
int hobby[NUM_HOUSES] = {0, 1, 2, 3, 4};
// String arrays for the final answer
const char *nationalities[] = {"Englishman", "Spaniard", "Ukrainian", "Norwegian", "Japanese"};
const char *pets[] = {"Dog", "Snails", "Fox", "Horse", "Zebra"};
// The main loop structure
do { // Nationality permutations
do { // Color permutations
// Rule 10: The Norwegian lives in the first house.
if (nationality[0] != NORWEGIAN) continue;
// Rule 15: The Norwegian lives next to the blue house.
if (color[1] != BLUE) continue;
do { // Pet permutations
do { // Beverage permutations
// Rule 9: Milk is drunk in the middle house.
if (beverage[2] != MILK) continue;
do { // Hobby permutations
// --- START OF FULL RULE CHECKING ---
bool rules_ok = true;
for (int i = 0; i < NUM_HOUSES; i++) {
// Rule 2: The Englishman lives in the red house.
if ((nationality[i] == ENGLISHMAN && color[i] != RED) || (nationality[i] != ENGLISHMAN && color[i] == RED)) {
rules_ok = false; break;
}
// Rule 3: The Spaniard owns the dog.
if ((nationality[i] == SPANIARD && pet[i] != DOG) || (nationality[i] != SPANIARD && pet[i] == DOG)) {
rules_ok = false; break;
}
// ... and so on for all 15 rules ...
}
if (rules_ok) {
// If we reach here, a solution is found!
solution_t solution = {NULL, NULL};
for (int i = 0; i < NUM_HOUSES; i++) {
if (beverage[i] == WATER) {
solution.water_drinker = nationalities[nationality[i]];
}
if (pet[i] == ZEBRA) {
solution.zebra_owner = nationalities[nationality[i]];
}
}
if (solution.water_drinker && solution.zebra_owner) {
return solution; // Return the final answer
}
}
// --- END OF FULL RULE CHECKING ---
} while (next_permutation(hobby));
} while (next_permutation(beverage));
} while (next_permutation(pet));
} while (next_permutation(color));
} while (next_permutation(nationality));
// Should be unreachable if a solution exists
return (solution_t){"Not Found", "Not Found"};
}
The Rule-Checking Logic Explained
Inside the innermost loop, we have a complete configuration. Now we must validate it against all 15 rules. The code iterates through each of the five houses (i = 0 to 4) and checks the rules.
There are three types of rules:
- Direct Association Rules: These link two attributes in the same house. For example, "The Englishman lives in the red house."
Implementation:if (nationality[i] == ENGLISHMAN && color[i] != RED) { /* fail */ }. The solution code uses a more robust check to ensure the link is exclusive:(A && !B) || (!A && B). This confirms that if you find the Englishman, his house MUST be red, and if you find the red house, its resident MUST be the Englishman. - Positional Rules: These relate to a specific house number. For example, "The Norwegian lives in the first house."
Implementation: This is checked directly using the index:if (nationality[0] != NORWEGIAN) { /* fail */ }. These checks are best done in the outer loops to prune the search space early. - Relative Positional Rules: These link attributes in adjacent houses. For example, "The green house is immediately to the right of the ivory house."
Implementation: This requires checking indicesiandi-1.if (color[i] == GREEN && color[i-1] != IVORY) { /* fail */ }. You must be careful to handle the edge case for the first house (i=0) wherei-1is out of bounds.
The code iterates through all houses and checks every rule. If any rule is violated for any house, a flag rules_ok is set to false, and the inner loop breaks, moving to the next permutation. If the loop completes with rules_ok still true, we have found the one and only solution.
Part 3: Compiling and Running
To use this solver, you would create a main.c file to call the function and print the results.
// main.c
#include <stdio.h>
#include "zebra_puzzle.h"
int main(void) {
solution_t result = solve_puzzle();
printf("--- Zebra Puzzle Solution ---\n");
printf("Who drinks water? The %s.\n", result.water_drinker);
printf("Who owns the zebra? The %s.\n", result.zebra_owner);
return 0;
}
You can compile all the files together using a C compiler like GCC. Make sure both zebra_puzzle.c and main.c are in the same directory.
# Compile the source files into an executable named 'solver'
gcc -o solver main.c zebra_puzzle.c -std=c11 -O2
# Run the executable
./solver
The output will reveal the long-awaited answers to the puzzle's two central questions.
Pros and Cons of the Brute-Force Permutation Approach
This method is powerful but has its trade-offs. Understanding them is crucial for knowing when to apply this strategy to other problems.
| Pros | Cons |
|---|---|
| Guaranteed Solution: If a solution exists, this method will find it. It exhaustively checks every single possibility, leaving no stone unturned. | Inefficient at Scale: The complexity is factorial (O(n!)). For 5 houses, it's manageable. For 6, it becomes much slower. For 10, it would be computationally infeasible. |
Conceptually Simple: The core idea of "try everything and check" is easy to understand, even if the implementation of next_permutation is intricate. |
Verbose Rule Implementation: Translating each of the 15 rules into C code results in a large, potentially error-prone block of `if` statements. |
| Excellent Learning Exercise: Implementing this solution provides deep insights into algorithms, data modeling, and low-level logical control in C. | Not Adaptable: If the puzzle rules change slightly, it requires significant code modification. It's not a flexible constraint-solving engine. |
Frequently Asked Questions (FAQ)
Is the Zebra Puzzle really Einstein's riddle?
There is no evidence to suggest Albert Einstein invented this puzzle. Its first known appearance was in Life International magazine in 1962. The puzzle's complexity led to it being popularly associated with the famous physicist, but this is widely considered a myth.
Why use permutations instead of a more advanced algorithm like backtracking?
For a small and fixed problem size like this (N=5), a brute-force permutation approach is perfectly feasible and often simpler to implement than a recursive backtracking solver. Backtracking shines when the search space can be pruned more effectively mid-generation, but the setup for this puzzle makes the full permutation approach a valid and understandable starting point.
Can this C code be optimized further?
Yes. The biggest optimization would be to "prune the search tree." This means checking rules as early as possible. For example, the rules "Norwegian is in the first house" and "Milk is in the middle house" can be checked in outer loops, not the innermost one. This would prevent the program from generating billions of invalid combinations, drastically speeding up the execution time.
What is a lexicographical permutation?
Lexicographical order is essentially "dictionary order." When applied to numbers, it means generating permutations in an increasing sequence. For example, for `{0, 1, 2}`, the lexicographical permutations are: `{0, 1, 2}`, `{0, 2, 1}`, `{1, 0, 2}`, `{1, 2, 0}`, `{2, 0, 1}`, and `{2, 1, 0}`.
How would this solution handle 6 houses instead of 5?
The code would need to be modified (e.g., change NUM_HOUSES to 6). However, the performance would degrade significantly. The number of permutations for one category would jump from 5! (120) to 6! (720). The total number of combinations to check would increase astronomically, making the brute-force approach very slow.
Why are C `enum`s better than using strings or magic numbers?
Enums provide type safety and readability. Using `if (nationality[i] == ENGLISHMAN)` is much clearer and less error-prone than `if (nationality[i] == 0)` or `if (strcmp(nationality[i], "Englishman") == 0)`. The compiler can catch typos (e.g., `ENGLSHMAN`), and integer comparisons are far faster than string comparisons.
Where can I learn more about constraint satisfaction problems?
Constraint Satisfaction Problems (CSPs) are a major topic in Artificial Intelligence and Operations Research. You can explore algorithms like backtracking, forward checking, and arc consistency. Resources like university AI courses (e.g., Berkeley's CS188) and books like "Artificial Intelligence: A Modern Approach" by Russell and Norvig provide comprehensive coverage.
Conclusion: From Logic to Executable
We have successfully journeyed from a classic logic puzzle to a fully functional C implementation. By representing the puzzle's abstract entities with C enums and employing a systematic permutation algorithm, we built a solver that can chew through billions of possibilities to find the single correct answer. This process highlights the raw power of computation to solve problems that are daunting for the human mind.
The key takeaway is not just the solution to the puzzle, but the methodology: model the problem's data, choose an appropriate algorithm (even a brute-force one), and translate the constraints into precise, logical code. This approach is a cornerstone of computational thinking and can be applied to countless other challenges you'll face in your programming career.
To continue your journey, we highly recommend exploring other algorithmic challenges. You can see the complete C guide for more foundational concepts or explore our C learning roadmap to discover your next challenge in the kodikra curriculum.
Technology Disclaimer: The code in this article is written using standard C (C11). It is compatible with most modern C compilers, including GCC and Clang. The algorithmic principles discussed are timeless and apply to any imperative programming language.
Published by Kodikra — Your trusted C learning resource.
Post a Comment