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
The zebra puzzle is a well-known logic puzzle. Many versions of the puzzle exist, including a version published in Life International magazine on December 17, 1962. The March 25, 1963, issue of Life contained the solution and the names of several hundred successful solvers from around the world.
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
As the Wikipedia page mentions, the Zebra Puzzle is related to a family of problems called 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
// 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.
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.
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.
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:
- Check if the all the variables inside the CSP are assigned, if yes return success, if not continue.
- Select an unassigned variable x.
- For each domain value, assign the value to the unassigned variable x.
- For each constraint check if it can be applied, if yes continue, if not skip to the next constraint.
- 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).
- Keep the assigned variable x and call this algorithm recursively.
- 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:
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 ✌️
Now we need to apply it to the Zebra Puzzle and we are done.
// 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.
mcaci
/
zebra-puzzle-example
A solution for the zebra puzzle in Go
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!
Top comments (0)