Scroll back to the top

The Zebra Puzzle brute force solution in golang

[ golang, brute-force, zebra-puzzle ]

In CS theory book I found the link on interesting Boolean Algebra task. The Zebra Puzzle It’s a sort of Boolean Algebra exercise.

I wrote simple golang program to solve the puzzle.

It’s a kind of pure brute force iterator of all possible combinations. Generator pattern is used to provide the combinations and implemented by goroutine and channel. It looks like standard approach in golang. It’s optimized to cut false combinations as soon as possible. There is also a DSL to describe a set of rules.

// Brute-force solution of the Zebra Puzzle
// https://code.energy/solving-zebra-puzzle/
//
// Result:
// Norwegian from 1 house drinks water.
// Japanese from 5 house owns zebra.

package main

import (
  "fmt"
)

func contains(values []int, value int) bool {
  for _, n := range values {
    if n == value {
      return true
    }
  }
  return false
}

func addIndexRecursive(indexes []int, ch chan []int, n int) {
  if len(indexes) == 5 {
    ch <- indexes
    return
  }
  for i := 0; i < n ; i++ {
    if contains(indexes, i) {
      continue
    }
    indexes = append(indexes, i)
    addIndexRecursive(indexes, ch, n)
    indexes = indexes[:len(indexes)-1]
  }
}

func allCombinations(n int) chan []int {
  ch := make(chan []int)
  go func(ch chan []int) {
    indexes := []int {}
    addIndexRecursive(indexes, ch, n)
    close(ch)
  }(ch)
  return ch
}


func match(indexes1 []int, value1 int, indexes2[]int, value2 int) bool {
  if (indexes1[0] != value1 || indexes2[0] != value2) &&
    (indexes1[1] != value1 || indexes2[1] != value2) &&
    (indexes1[2] != value1 || indexes2[2] != value2) &&
    (indexes1[3] != value1 || indexes2[3] != value2) &&
    (indexes1[4] != value1 || indexes2[4] != value2) {
    return false
  }
  return true
}

func rightOf(indexes1 []int, value1 int, indexes2[]int, value2 int) bool {
  if (indexes1[1] != value1 || indexes2[0] != value2) &&
    (indexes1[2] != value1 || indexes2[1] != value2) &&
    (indexes1[3] != value1 || indexes2[2] != value2) &&
    (indexes1[4] != value1 || indexes2[3] != value2) {
    return false
  }
  return true
}

func nextTo(indexes1 []int, value1 int, indexes2[]int, value2 int) bool {
  if (indexes1[0] != value1 || indexes2[1] != value2) &&
    (indexes1[1] != value1 || indexes2[0] != value2 && indexes2[2] != value2) &&
    (indexes1[2] != value1 || indexes2[1] != value2 && indexes2[3] != value2) &&
    (indexes1[3] != value1 || indexes2[2] != value2 && indexes2[4] != value2) &&
    (indexes1[4] != value1 || indexes2[3] != value2) {
    return false
  }
  return true
}

const (
  englishman = iota
  ukrainian
  norwegian
  japanese
  spaniard
)

const (
  red = iota
  green
  ivory
  blue
  yellow
)

const (
  milk = iota
  orange
  water
  tea
  coffee
)

const (
  oldGold = iota
  kools
  chesterfields
  luckyStrike
  parliaments
)

const (
  dog = iota
  snails
  horse
  zebra
  fox
)

func main() {
  nationsTitles := [5]string {"Englishman", "Ukrainian", "Norwegian", "Japanese", "Spaniard"}

  for iNations := range allCombinations(5) {
    if !(iNations[0] == norwegian) {
      continue
    }
    for iSmokes := range allCombinations(5) {
      if !match(iNations, japanese, iSmokes, parliaments) {
        continue
      }
      for iColors := range allCombinations(5) {
        if !match(iNations, englishman, iColors, red) ||
          !match(iSmokes, kools, iColors, yellow) ||
          !rightOf(iColors, green, iColors, ivory) ||
          !nextTo(iNations, norwegian, iColors, blue) {
          continue
        }
        for iDrinks := range allCombinations(5) {
          if !(iDrinks[2] == 0) ||
            !match(iDrinks, coffee, iColors, green) ||
            !match(iNations, ukrainian, iDrinks, tea) ||
            !match(iSmokes, luckyStrike, iDrinks, orange) {
            continue
          }
          for iPets := range allCombinations(5) {
            if !match(iNations, spaniard, iPets, dog) ||
              !match(iSmokes, oldGold, iPets, snails) ||
              !nextTo(iSmokes, chesterfields, iPets, fox) ||
              !nextTo(iSmokes, kools, iPets, horse) {
              continue
            }

            for i, iDrink := range iDrinks {
              if iDrink == water {
                fmt.Println(nationsTitles[iNations[i]], "from", i + 1, "house drinks water.")
              }
            }
            for i, iPet := range iPets {
              if iPet == zebra {
                fmt.Println(nationsTitles[iNations[i]], "from", i + 1, "house owns zebra.")
              }
            }
          }
        }
      }
    }
  }
}