<div class="notebook">

<div class="nb-cell markdown" name="md1">
# Solving Zebra puzzles with Prolog

_Robert Laing_

Something I’ve found fun and educational is solving the kind of logic puzzles that involve filling out a table, known as a
[Zebra puzzle](https://en.wikipedia.org/wiki/Zebra_Puzzle).

These are very easy to do with Prolog, illustrating the power of _unification_ and other basic concepts.

I found a book of these in a remainder sale a while back and the first one goes like this:

&gt; Tackfield St Andrew is a lovely little Suffolk village whose inhabitants are very conservative – they still refer to a number of retired Londoners who moved there years ago as ‘the new people’. From the clues below, can you work out where in London each of ‘the new people’ came from, how long they’ve lived in the village, and the name of each one’s home there?

It has a diagram which shows there are four variables with three values each:

```
Names: Alan Bradley, Mavis Norton, Walter Young
Area: Battersea, Islington, Paddington
Period: 8, 11, 16 years
House: Meadow View, Rose Cottage, White Gates
```

Then there are four clues to fit these together:

 1. Walter Young, who lives at Meadow View, is not the former Londoner who used to live and work in Islington.
 2. The person whose ex-home was just behind Paddington railway station has lived in Tackfield St Andrew longer than Alan Bradley.
 3. The Resident in White Gates has lived in the village for more than 8 years.
 4. One of the ‘new people’ has actually been living at Rose Cottage for 16 years.

I translated this into Prolog as follows
</div>

<div class="nb-cell program" name="p1">
puzzle(People) :-
    People = [newpeople(_, _,  8, _), 
              newpeople(_, _, 11, _), 
              newpeople(_, _, 16, 'Rose Cottage')],
    member(newpeople('Alan Bradley', _, Period1, _), People),
    member(newpeople('Mavis Norton', _, _, _), People),
    member(newpeople('Walter Young', _, _, 'Meadow View'), People),
    member(newpeople(_, _, Period2, 'White Gates'), People),
    member(newpeople(_, 'Battersea', _, _), People),
    member(newpeople(_, 'Islington', _, _), People),
    member(newpeople(_, 'Paddington', Period3, _), People),
    \+member(newpeople('Walter Young', 'Islington', _, _), People),
    Period2 &gt; 8,
    Period3 &gt; Period1.
</div>

<div class="nb-cell query" data-chunk="7" data-tabled="true" name="q1">
puzzle(_People),
member(newpeople(Name, Area, Period, House), _People).
</div>

<div class="nb-cell markdown" name="md2">
The above example only has one solution, making it _deterministic_ in Prolog jargon. The original Zebra puzzle published in 1962 by Life Magazine had unique answers for its two questions "Now, who drinks water? Who owns the zebra?", it had an ambiguity which would make Prolog give two alternative answers, making in _nondeterministic_.
</div>

</div>