Solving the Zebra Puzzle using Go
Tags: go, zebrapuzzle, csp
Published: 2020-04-30 10:28:25

---
title: Solving the Zebra Puzzle using Go
published: true
description: A Go implementation for a constraint satisfaction problem
tags: go,golang,zebrapuzzle,csp
cover_image: https://miro.medium.com/max/848/1*yI6PbqgcDFwmD2qEz7ODQA.png
---
In this article I want to share the steps that I followed to solve the Zebra Puzzle problem in Go and the algorithm that hides behind its solution.
#What is the Zebra Puzzle
{% wikipedia https://en.wikipedia.org/wiki/Zebra_Puzzle %} 
The Zebra Puzzle is a logic problem that may have several formulations, one of which is the following:

_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._
_The Norwegian lives in the first house._
_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._
_Now, who drinks water? Who owns the zebra?_

The answer of this puzzle is determined by checking all the constraints and building the solution step by step. More details about the problem and the solution can be found in the Wikipedia reference. Let’s see how we can code the solution in Go.

# Developing the solution
![Our gopher is ready!](https://dev-to-uploads.s3.amazonaws.com/i/d1qgdhkmapddgo3kcd8p.png)
<figcaption>Our gopher is ready!</figcaption>

As the Wikipedia page mentions, the Zebra Puzzle is related to a family of problems called _[Constraint Satisfaction Problem](https://en.wikipedia.org/wiki/Constraint_satisfaction_problem) (CSP)_.

A CSP is composed of a __Variable set__, a __Domain set__ and a __Constraint set__ and the problem is solved when all the variables are assigned domain values for which all constraints are satisfied.

#Defining and implementing our CSP for the Zebra Puzzle
Let’s define a simple `struct` to define our CSP

```go
// CSP is a structure that models a simple constraint satisfaction problem
type CSP struct {
	v, d []uint8
	c    []constrainter
}
```

__v, the Variable set__: for the Zebra Puzzle there are 30 variables, 1 per every available value in the puzzle.
At implementation time it is just a slice of 30 `uint8` values as in `v: make([]uint8, 30)`

__d, the Domain set__: for the Zebra Puzzle there are 30 values, 5 different values for each of the 6 available categories (nationality, pet, drink, smoke, house color and house number).
For the implementation, we assume that we can map all the problem values with positive integers from 1 to 5 according to their category.

```go
type domainer interface {
	toDomainVal() uint8
}

type nationality uint8

const (
	norwegian nationality = iota + 1
	spaniard
	englishman
	ukrainian
	japanese
)

func (n nationality) toDomainVal() uint8 { return uint8(n) }
```

Which means our domain set is implemented in our struct as `d: []uint8{1, 2, 3, 4, 5}`

__c, the Constraint set__: for the Zebra Puzzle there are 15 constraints, 14 explicitly mentioned in the puzzle statements,1 mentioned afterwards that states that every value cannot appear in the solution more than once.

```go
type constrainter interface {
	forSatisfaction() constraint
	forApplicability() constraint
}

type constraint func(...uint8) bool
```

If you noticed the struct definition I use a type called constrainter. However to avoid things getting confusing let’s just focus on the __constraint__ type.
_A **constraint** is a function that evaluates to true or false after examining a sequence of uint8 values._

__Example of constraint__: given an sequence of variables, read its values by groups of 5 elements and verify that every element in the group is different or equal to 0 (which is an unassigned variable), which means __check if an assignment is a partial solution to the CSP__.

```go
func partialSolution(assignment ...uint8) bool {
	var count []uint8
	for i, v := range assignment {
		if i%5 == 0 {
			count = make([]uint8, 6)
		}
		count[v]++
		if v == 0 || count[v] == 1 {
			continue
		}
		return false
	}
	return true
}
```

At this point solving the Zebra Puzzle is a matter of assigning values from `d` to the variables in `v` making sure that all constraints in `c` are satisfied.

#Solving the CSP in Go

A typical solution to a CSP is a recursive backtracking algorithm:

1. Check if the all the variables inside the CSP are assigned, if yes return success, if not continue.
2. Select an unassigned variable x.
3. For each domain value, assign the value to the unassigned variable x.
4. For each constraint check if it can be applied, if yes continue, if not skip to the next constraint.
5. If the constraint can be applied, check if the current set of variables satisfy the constraint, if yes continue to step 6, if not unassign the variable x and skip to the next domain value (step 3).
6. Keep the assigned variable x and call this algorithm recursively.
7. If all domain values are looped without satisfying the constraint set a failure is returned and we backtrack one step down.

Or in the code:

```go
func recursiveBacktracking(assignment *[]uint8, csp *CSP) bool {
	if complete(csp.v) {
		return true
	}
	idx := selectUnassigned(&csp.v, assignment, *csp)
domainValueLoop:
	for _, d := range csp.d {
		csp.v[idx] = d
		for _, c := range csp.c {
			switch {
			case !c.forApplicability()(csp.v...):
				continue
			case !c.forSatisfaction()(csp.v...):
				csp.v[idx] = 0
				continue domainValueLoop
			default:
			}
		}
		outcome := recursiveBacktracking(assignment, csp)
		if !outcome {
			csp.v[idx] = 0
			continue domainValueLoop
		}
		return true
	}
	return false
}
```

And that’s it! The main algorithm for solving a CSP problem is ready :v:

Now we need to apply it to the Zebra Puzzle and we are done.

```go
// SolvePuzzle function solves the zebra puzzle
func SolvePuzzle() Solution {
	csp := CSP{
		v: make([]uint8, 30),
		d: []uint8{1, 2, 3, 4, 5},
		c: []constrainter{
			constraint(partialSolution),
			togetherWithConstraint{a: englishman, b: red},
			togetherWithConstraint{a: green, b: coffee},
			togetherWithConstraint{a: spaniard, b: dog},
			togetherWithConstraint{a: ukrainian, b: tea},
			toTheRightOfConstraint{a: green, b: ivory},
			togetherWithConstraint{a: oldGold, b: snails},
			togetherWithConstraint{a: kools, b: yellow},
			togetherWithConstraint{a: milk, b: house3},
			togetherWithConstraint{a: norwegian, b: house1},
			nextToConstraint{a: chesterfields, b: fox},
			nextToConstraint{a: kools, b: horse},
			togetherWithConstraint{a: luckyStrike, b: orangeJuice},
			togetherWithConstraint{a: japanese, b: parliaments},
			nextToConstraint{a: norwegian, b: blue},
		},
	}
	recursiveBacktracking(&csp.v, &csp)
	return Solution{OwnsZebra: ownerOf(zebra, csp.v...), DrinksWater: ownerOf(water, csp.v...)}
}
```

The technical details of the implementation for this specific Zebra Puzzle solution are located in my zebra-puzzle-example GitHub repository.

{% github mcaci/zebra-puzzle-example %}

Inside it there are the details on the modeling of the domain values and the details about all the different types implementing the `constrainter` interface (like `constraint`, `togetherWithConstraint`, `nextToConstraint`, `toTheRightConstraint`) and implementations of the applicability and satisfatibiliy functions.

#Parting thoughts

The Zebra Puzzle is a challenging problem to solve which can become easier with the right tools and approach. In this article we started by defining the problem, we found the category to which it belongs, we modeled its solution and developed its algorithm.

For the moment I’ll leave to the reader with the generic concepts of the CSP, in a further article, if desired, I might detail some of the implementation choices I have taken to implement the solution such as the usage of interfaces, interface embedding and type aliasing.

You can find me up on twitter @nikiforos_frees if you have any questions or comments and follow me on dev.to @mcaci

**This was Michele and thanks for reading!**