Exercism - Zebra Puzzle

Preparation

Before we click on our next exercise, let’s see what concepts of DART we need to consider

So we need to use the following concepts.

Generator Functions (sync* and yield)

Generator functions use sync* and yield to create iterables lazily. They’re perfect for generating large solution spaces without creating all solutions in memory at once.

Iterable<int> generateNumbers() sync* {
  for (int i = 1; i <= 5; i++) {
    yield i; // Yield each value lazily
  }
}

Iterable<List<int>> generatePermutations(List<int> items) sync* {
  if (items.length <= 1) {
    yield items;
    return;
  }
  
  for (var i = 0; i < items.length; i++) {
    final current = items[i];
    final remaining = [...items.sublist(0, i), ...items.sublist(i + 1)];
    
    for (final perm in generatePermutations(remaining)) {
      yield [current, ...perm];
    }
  }
}

void main() {
  // Lazy evaluation - only computes what's needed
  final perms = generatePermutations([1, 2, 3]);
  print(perms.take(2).toList()); // Only generates first 2 permutations
}

Permutations

Permutations are all possible arrangements of a set of items. Generating permutations is essential for constraint satisfaction problems where we need to try all possible combinations.

Iterable<List<T>> permutations<T>(List<T> items) sync* {
  if (items.length <= 1) {
    yield items;
    return;
  }
  
  for (var i = 0; i < items.length; i++) {
    final current = items[i];
    final remaining = [...items.sublist(0, i), ...items.sublist(i + 1)];
    
    for (final perm in permutations(remaining)) {
      yield [current, ...perm];
    }
  }
}

void main() {
  final perms = permutations(['a', 'b', 'c']);
  for (final perm in perms) {
    print(perm); // [a, b, c], [a, c, b], [b, a, c], etc.
  }
}

List `indexOf()` Method

The indexOf() method returns the index of the first occurrence of an element in a list. It’s essential for finding which house has a specific attribute.

void main() {
  List<String> houses = ['red', 'green', 'blue', 'yellow', 'ivory'];
  
  // Find index of element
  int redIndex = houses.indexOf('red');
  print(redIndex); // 0
  
  int greenIndex = houses.indexOf('green');
  print(greenIndex); // 1
  
  // Use for constraint checking
  List<String> nationalities = ['Englishman', 'Spaniard', 'Ukrainian', 'Norwegian', 'Japanese'];
  int englishIndex = nationalities.indexOf('Englishman');
  int redIndex2 = houses.indexOf('red');
  
  // Check if Englishman is in red house
  if (englishIndex == redIndex2) {
    print('Constraint satisfied');
  }
}

Iterable `where()` Method

The where() method filters an iterable based on a condition. It’s perfect for applying constraints to filter out invalid permutations.

void main() {
  List<int> numbers = [1, 2, 3, 4, 5];
  
  // Filter even numbers
  var evens = numbers.where((n) => n % 2 == 0);
  print(evens.toList()); // [2, 4]
  
  // Filter permutations with constraints
  Iterable<List<String>> colorPerms = generatePermutations(['red', 'green', 'blue']);
  var validPerms = colorPerms.where((colors) {
    int greenIdx = colors.indexOf('green');
    int redIdx = colors.indexOf('red');
    return greenIdx == redIdx + 1; // Green immediately right of red
  });
}

Spread Operator (`...`)

The spread operator (...) expands a list into individual elements. It’s useful for combining lists when generating permutations.

void main() {
  List<int> list1 = [1, 2];
  List<int> list2 = [3, 4];
  
  // Combine lists
  List<int> combined = [...list1, ...list2];
  print(combined); // [1, 2, 3, 4]
  
  // Use in permutations
  List<int> items = [1, 2, 3];
  int current = items[0];
  List<int> remaining = [...items.sublist(0, 0), ...items.sublist(1)];
  print(remaining); // [2, 3]
  
  // Prepend element
  List<int> withCurrent = [current, ...remaining];
  print(withCurrent); // [1, 2, 3]
}

List `sublist()` Method

The sublist() method creates a new list containing elements from a specified range. It’s essential for generating permutations recursively.

void main() {
  List<int> items = [1, 2, 3, 4, 5];
  
  // Get sublist from index to end
  List<int> rest = items.sublist(1);
  print(rest); // [2, 3, 4, 5]
  
  // Get sublist with start and end
  List<int> middle = items.sublist(1, 4);
  print(middle); // [2, 3, 4]
  
  // Use in permutations
  int i = 2;
  List<int> before = items.sublist(0, i); // [1, 2]
  List<int> after = items.sublist(i + 1); // [4, 5]
  List<int> remaining = [...before, ...after]; // [1, 2, 4, 5]
}

Absolute Value (`abs()`)

The abs() method returns the absolute value of a number. It’s useful for checking if two positions are adjacent.

void main() {
  int a = 2;
  int b = 3;
  
  // Check if adjacent
  bool adjacent = (a - b).abs() == 1;
  print(adjacent); // true
  
  // Examples
  print((0 - 1).abs()); // 1 (adjacent)
  print((0 - 2).abs()); // 2 (not adjacent)
  print((1 - 2).abs()); // 1 (adjacent)
  
  // Use for constraint checking
  int house1 = 2;
  int house2 = 3;
  if ((house1 - house2).abs() == 1) {
    print('Houses are next to each other');
  }
}

Continue Statement

The continue statement skips the rest of the current loop iteration and moves to the next iteration. It’s useful for early exit when constraints aren’t satisfied.

void main() {
  for (int i = 0; i < 10; i++) {
    if (i % 2 == 0) {
      continue; // Skip even numbers
    }
    print(i); // Only prints odd numbers: 1, 3, 5, 7, 9
  }
  
  // Use in constraint checking
  for (final colors in colorPermutations) {
    if (colors.indexOf('red') != nationalities.indexOf('Englishman')) {
      continue; // Skip this permutation, constraint not satisfied
    }
    // Process valid permutation
  }
}

Required Named Parameters

Required named parameters must be provided when calling a function. They’re marked with the required keyword and make function calls more explicit.

class Solution {
  final String drinksWater;
  final String ownsZebra;
  
  // Required named parameters
  Solution({required this.drinksWater, required this.ownsZebra});
}

void main() {
  // Must provide both parameters
  Solution solution = Solution(
    drinksWater: 'Norwegian',
    ownsZebra: 'Japanese',
  );
  
  // Cannot omit required parameters
  // Solution solution2 = Solution(); // Error
}

Nullable Fields

Nullable fields can hold either a value or null. They’re useful for storing results that are computed later.

class ZebraPuzzle {
  String? drinksWater; // Nullable - will be set after solving
  String? ownsZebra;   // Nullable - will be set after solving
  
  void solve() {
    // Compute solution
    drinksWater = 'Norwegian';
    ownsZebra = 'Japanese';
  }
}

void main() {
  ZebraPuzzle puzzle = ZebraPuzzle();
  print(puzzle.drinksWater); // null (not solved yet)
  
  puzzle.solve();
  print(puzzle.drinksWater); // 'Norwegian'
}

Nested Loops

Nested loops allow you to iterate through multiple dimensions. They’re essential for trying all combinations of different attributes.

void main() {
  // Try all combinations
  for (final colors in colorPermutations) {
    for (final nationalities in nationalityPermutations) {
      for (final drinks in drinkPermutations) {
        // Check constraints
        if (satisfiesConstraints(colors, nationalities, drinks)) {
          // Found valid combination
          return;
        }
      }
    }
  }
}

Constraint Satisfaction

Constraint satisfaction problems (CSP) involve finding values that satisfy a set of constraints. The key is to:

Generate all possible combinations
Filter by constraints early (pruning)
Check remaining constraints as you go

void main() {
  // Apply constraints in order of restrictiveness
  // Most constrained first (fewer possibilities)
  
  // Constraint 1: Norwegian in first house
  var nationalities = nationalityPerms.where((n) => n[0] == 'Norwegian');
  
  // Constraint 2: Green right of ivory
  var colors = colorPerms.where((c) {
    return c.indexOf('green') == c.indexOf('ivory') + 1;
  });
  
  // Continue filtering with more constraints...
}

Introduction

The Zebra Puzzle is a famous logic puzzle in which there are five houses, each painted a different color. The houses have different inhabitants, who have different nationalities, own different pets, drink different beverages and enjoy different hobbies.

To help you solve the puzzle, you’re given 15 statements describing the solution. However, only by combining the information in all statements will you be able to find the solution to the puzzle.

Note

The Zebra Puzzle is a Constraint satisfaction problem (CSP). In such a problem, you have a set of possible values and a set of constraints that limit which values are valid. Another well-known CSP is Sudoku.

Instructions

Your task is to solve the Zebra Puzzle to find the answer to these two questions:

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

Puzzle

The following 15 statements are all known to be true:

There are five houses.
The Englishman lives in the red house.
The Spaniard owns the dog.
The person in the green house drinks coffee.
The Ukrainian drinks tea.
The green house is immediately to the right of the ivory house.
The snail owner likes to go dancing.
The person in the yellow house is a painter.
The person in the middle house drinks milk.
The Norwegian lives in the first house.
The person who enjoys reading lives in the house next to the person with the fox.
The painter’s house is next to the house with the horse.
The person who plays football drinks orange juice.
The Japanese person plays chess.
The Norwegian lives next to the blue house.

Additionally, each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and engage in different hobbies.

Note

There are 24 billion (5!⁵ = 24,883,200,000) possible solutions, so try ruling out as many solutions as possible.

How do we solve the Zebra Puzzle?

To solve this constraint satisfaction problem:

Generate permutations: Create all possible arrangements for each attribute (nationality, color, drink, hobby, pet)
Apply constraints early: Filter permutations using the most restrictive constraints first to reduce search space
Nested iteration: Try all combinations of filtered permutations
Check constraints: For each combination, verify all constraints are satisfied
Find solution: When a valid combination is found, extract the answers

Key optimizations:

Start with most constrained variables (Norwegian in first house)
Use generators for lazy evaluation (don’t generate all permutations upfront)
Apply constraints as early as possible (filter before nested loops)
Use continue to skip invalid combinations early

Constraint order (most to least restrictive):

Norwegian in first house (reduces nationalities from 120 to 24)
Green right of ivory + Norwegian next to blue (reduces colors significantly)
Englishman in red house (further reduces combinations)
Middle house drinks milk (reduces drinks)
Continue with remaining constraints…

Solution

class ZebraPuzzle {
  String? drinksWater;
  String? ownsZebra;

  void solve() {
    // Use sync* generators for lazy evaluation - only compute what we need
    final solutions = _generateSolutions();
    
    for (final solution in solutions) {
      drinksWater = solution.drinksWater;
      ownsZebra = solution.ownsZebra;
      return; // Found the solution!
    }
  }

  Iterable<Solution> _generateSolutions() sync* {
    // Start with most constrained variables (fewest possibilities)
    // Constraint 10: Norwegian in first house
    final nationalityPerms = _permutations(['Englishman', 'Spaniard', 'Ukrainian', 'Norwegian', 'Japanese'])
        .where((n) => n[0] == 'Norwegian');

    for (final nationalities in nationalityPerms) {
      // Constraint 6: green immediately right of ivory
      // Constraint 15: Norwegian next to blue (house 0 or 1)
      final colorPerms = _permutations(['red', 'green', 'ivory', 'yellow', 'blue']).where((colors) {
        final greenIdx = colors.indexOf('green');
        final ivoryIdx = colors.indexOf('ivory');
        final blueIdx = colors.indexOf('blue');
        
        return greenIdx == ivoryIdx + 1 && // green right of ivory
               (blueIdx - 0).abs() == 1;    // Norwegian (at 0) next to blue
      });

      for (final colors in colorPerms) {
        // Constraint 2: Englishman in red house
        if (nationalities.indexOf('Englishman') != colors.indexOf('red')) continue;

        // Constraint 9: middle house drinks milk
        // Constraint 4: green house drinks coffee
        // Constraint 5: Ukrainian drinks tea
        final drinkPerms = _permutations(['coffee', 'tea', 'milk', 'orange juice', 'water']).where((drinks) {
          return drinks[2] == 'milk' &&
                 colors.indexOf('green') == drinks.indexOf('coffee') &&
                 nationalities.indexOf('Ukrainian') == drinks.indexOf('tea');
        });

        for (final drinks in drinkPerms) {
          // Constraint 8: yellow house has painter
          // Constraint 13: football player drinks orange juice
          // Constraint 14: Japanese plays chess
          final hobbyPerms = _permutations(['dancing', 'painting', 'reading', 'football', 'chess']).where((hobbies) {
            return colors.indexOf('yellow') == hobbies.indexOf('painting') &&
                   hobbies.indexOf('football') == drinks.indexOf('orange juice') &&
                   nationalities.indexOf('Japanese') == hobbies.indexOf('chess');
          });

          for (final hobbies in hobbyPerms) {
            // Constraint 3: Spaniard owns dog
            // Constraint 7: snail owner likes dancing
            // Constraint 11: reader next to fox
            // Constraint 12: painter next to horse
            final petPerms = _permutations(['dog', 'snail', 'fox', 'horse', 'zebra']).where((pets) {
              return nationalities.indexOf('Spaniard') == pets.indexOf('dog') &&
                     pets.indexOf('snail') == hobbies.indexOf('dancing') &&
                     _isAdjacent(hobbies.indexOf('reading'), pets.indexOf('fox')) &&
                     _isAdjacent(hobbies.indexOf('painting'), pets.indexOf('horse'));
            });

            for (final pets in petPerms) {
              yield Solution(
                drinksWater: nationalities[drinks.indexOf('water')],
                ownsZebra: nationalities[pets.indexOf('zebra')],
              );
            }
          }
        }
      }
    }
  }

  bool _isAdjacent(int a, int b) => (a - b).abs() == 1;

  Iterable<List<T>> _permutations<T>(List<T> items) sync* {
    if (items.length <= 1) {
      yield items;
      return;
    }

    for (var i = 0; i < items.length; i++) {
      final current = items[i];
      final remaining = [...items.sublist(0, i), ...items.sublist(i + 1)];

      for (final perm in _permutations(remaining)) {
        yield [current, ...perm];
      }
    }
  }
}

class Solution {
  final String drinksWater;
  final String ownsZebra;

  Solution({required this.drinksWater, required this.ownsZebra});
}

Let’s break down the solution:

class ZebraPuzzle - Main puzzle solver:
- Encapsulates the solving logic
- Stores results in nullable fields
String? drinksWater and String? ownsZebra - Result fields:
- Nullable fields that will be set after solving
- Initially null, set when solution is found
void solve() - Public solve method:
- Generates solutions lazily using generator
- Takes first solution (there should be only one)
- Sets result fields and returns
Iterable<Solution> _generateSolutions() sync* - Solution generator:
- Generator function that yields valid solutions
- Uses lazy evaluation (only computes what’s needed)
- Applies constraints in order of restrictiveness
_permutations(['Englishman', ...]).where((n) => n[0] == 'Norwegian') - Filter nationalities:
- Generates all nationality permutations
- Filters to only those with Norwegian in first house (Constraint 10)
- Reduces from 120 to 24 possibilities
for (final nationalities in nationalityPerms) - Iterate nationalities:
- Try each valid nationality arrangement
- Nested loops will try all combinations
_permutations(['red', ...]).where((colors) => ...) - Filter colors:
- Generates all color permutations
- Filters by constraints:
  - Green immediately right of ivory (Constraint 6)
  - Norwegian (at index 0) next to blue (Constraint 15)
if (nationalities.indexOf('Englishman') != colors.indexOf('red')) continue - Early exit:
- Checks Constraint 2: Englishman in red house
- Skips this combination if constraint not satisfied
- continue moves to next iteration
_permutations(['coffee', ...]).where((drinks) => ...) - Filter drinks:
- Generates all drink permutations
- Filters by constraints:
  - Middle house (index 2) drinks milk (Constraint 9)
  - Green house drinks coffee (Constraint 4)
  - Ukrainian drinks tea (Constraint 5)
_permutations(['dancing', ...]).where((hobbies) => ...) - Filter hobbies:
- Generates all hobby permutations
- Filters by constraints:
  - Yellow house has painter (Constraint 8)
  - Football player drinks orange juice (Constraint 13)
  - Japanese plays chess (Constraint 14)
_permutations(['dog', ...]).where((pets) => ...) - Filter pets:
- Generates all pet permutations
- Filters by constraints:
  - Spaniard owns dog (Constraint 3)
  - Snail owner likes dancing (Constraint 7)
  - Reader next to fox (Constraint 11)
  - Painter next to horse (Constraint 12)
_isAdjacent(hobbies.indexOf('reading'), pets.indexOf('fox')) - Adjacency check:
- Helper method checks if two positions are adjacent
- Uses absolute value: (a - b).abs() == 1
- Returns true if positions differ by 1
yield Solution(...) - Yield solution:
- When all constraints are satisfied, yield a solution
- Extracts answers:
  - drinksWater: nationality at index where drinks is ‘water’
  - ownsZebra: nationality at index where pets is ‘zebra’
bool _isAdjacent(int a, int b) => (a - b).abs() == 1 - Adjacency helper:
- Expression-bodied method
- Checks if two house indices are next to each other
- Uses absolute value of difference
Iterable<List<T>> _permutations<T>(List<T> items) sync* - Permutation generator:
- Recursive generator function
- Generates all permutations of a list
- Uses lazy evaluation (yields one at a time)
if (items.length <= 1) { yield items; return; } - Base case:
- If 0 or 1 items, only one permutation exists
- Yield it and return
for (var i = 0; i < items.length; i++) - Recursive case:
- For each item, use it as first element
- Generate permutations of remaining items
- Combine current with each permutation
final remaining = [...items.sublist(0, i), ...items.sublist(i + 1)] - Get remaining:
- Creates list without current item
- Uses spread operator to combine sublists
- Example: items=[1,2,3], i=1 → remaining=[1,3]
yield [current, ...perm] - Combine and yield:
- Prepends current item to each permutation
- Yields the combined permutation
- Example: current=2, perm=[1,3] → yield [2,1,3]
class Solution - Solution data class:
- Stores the two answers
- Uses required named parameters
- Immutable (final fields)

The solution efficiently solves the constraint satisfaction problem using lazy evaluation, early constraint filtering, and recursive permutation generation. By applying the most restrictive constraints first, it dramatically reduces the search space from 24 billion to a manageable number of combinations.

A video tutorial for this exercise is coming soon! In the meantime, check out my YouTube channel for more Dart and Flutter tutorials. 😉

Visit My YouTube Channel

Preparation

Generator Functions (sync* and yield)

Permutations

List indexOf() Method

Iterable where() Method

Spread Operator (...)

List sublist() Method

Absolute Value (abs())

Continue Statement

Required Named Parameters

Nullable Fields

Nested Loops

Constraint Satisfaction

Introduction

Note

Instructions

Puzzle

Note

How do we solve the Zebra Puzzle?

Solution

List `indexOf()` Method

Iterable `where()` Method

Spread Operator (`...`)

List `sublist()` Method

Absolute Value (`abs()`)