Zebra Puzzle (Prolog)

From LiteratePrograms

This article explains how to solve Zebra Puzzle in Prolog, one of the most popular logic programming languages. For an exact description of the puzzle, please refer to the corresponding article in Wikipedia.

Contents 1 Strategy 2 Rules 2.1 next_to rule 2.2 is_right rule 3 Facts 4 Execution result 5 External links

Strategy

First, we declare 15 facts using a number of rules. Then we ask who owns zebra.

<<Einstein.pro>>=
rules
query

We define house(C, N, P, D, S) predicate which signify the following information.

• C: the color of the house
• N: the nationality of the resident
• P: the resident's pet
• D: the resident's drink
• S: the resident's cigarette

With the aid of the anonymous variable '_', we can represent the fact "The Englishman lives in the red house." as a Prolog statement house(red, englishman, _, _, _).

Rules

next_to rule

The next_to(X, Y, List) rule is true if the elements X and Y are adjacent in the List. Internally, it employs is_right rule to check whether X is to the right of Y or Y is to the right of X.

<<rules>>=
next_to(X, Y, List) :- is_right(X, Y, List).
next_to(X, Y, List) :- is_right(Y, X, List).

is_right rule

Before we delve into is_right rule, we need to investigate basic list operation in Prolog. The head of a list L is the first element, while the tail is the list consisting of all elements of L except for the head. [X | Y] is a special notation for splitting lists into head X and tail Y.

The is_right rule is somewhat complex -- it is defined by recursion.

• boundary condition: is_right(L, R, [L | [R | _]] is true if the element L comes first in the list and the element R is at the second position.

<<rules>>=
is_right(L, R, [L | [R | _]]).

• recursive condition: R is at the right of L in a list if R is at the right of L in the tail of the list.

<<rules>>=
is_right(L, R, [_ | Rest]) :- is_right(L, R, Rest).

Facts

This section explains how to convert each fact into a predicate, Prolog's basic unit which is defined to be true. Note that every variable in Prolog must begin with a capital letter or an underscore. And every clause in Prolog must end with a period.

We define owns_zebra rules in order to find out which resident owns a zebra.

<<query>>=
owns_zebra(Street, Who) :-

The left part of rule delimiter ":-" is called head and the right part tail. Every predicate in the tail of this rule is concatenated by a comma "," because conjunction is written as a comma.

1. There are five houses
As we know that there are five house in a row, we declare Street list containing five elements. Note the comma in the end.

<<query>>=
  Street = [_House1, _House2, _House3, _House4, _House5],

2. The Englishman lives in the red house.
member(X, Y) is true if X is a member of the list Y. The red house where the Englishman lives is a member of the list Street.

<<query>>=
  member(house(red, englishman, _, _, _), Street),

3. The Spaniard owns the dog.

<<query>>=
  member(house(_, spaniard, dog, _, _), Street),

4. Coffee is drunk in the green house.

<<query>>=
  member(house(green, _, _, coffee, _), Street),

5. The Ukrainian drinks tea.

<<query>>=
  member(house(_, ukrainian, _, tea, _), Street),

6. The green house is immediately to the right of the ivory house. We employ is_right rule to denote the 'right relationship.'

<<query>>=
  is_right(house(green,_,_,_,_), house(ivory,_,_,_,_), Street),

7. The Old Gold smoker owns snails.

<<query>>=
  member(house(_, _, snails, _, old_gold), Street),

8. Kools are smoked in the yellow house.

<<query>>=
  member(house(yellow, _, _, _, kools), Street),

9. Milk is drunk in the middle house.

<<query>>=
  [_, _, house(_, _, _, milk, _), _, _] = Street,

10. The Norwegian lives in the first house.

<<query>>=
  [house(_, norwegian, _, _, _) | _] = Street,

11. The man who smokes Chesterfields lives in the house next to the man with the fox. Note the next_to rule.

<<query>>=
  next_to(house(_, _, _, _, chesterfields), house(_, _, fox, _, _), Street),

12. Kools are smoked in the house next to the house where the horse is kept.

<<query>>=
  next_to(house(_, _, _, _, kools), house(_, _, horse, _, _), Street),

13. The Lucky Strike smoker drinks orange juice.

<<query>>=
  member(house(_, _, _, orange_juice, lucky_strike), Street),

14. The Japanese smokes Parliaments.

<<query>>=
  member(house(_, japanese, _, _, parliaments), Street),

15. The Norwegian lives next to the blue house.

<<query>>=
  next_to(house(_, norwegian, _, _, _), house(blue, _, _, _, _), Street),

Finally, we ask who owns a zebra.

<<query>>=
  member(house(_, Who, zebra, _, _), Street).

The rule must end with a period.

Execution result

The execution result is shown below. We use SWI-Prolog interpreter under Windows-XP. The output is pretty-printed by hand for better alignment.

% e:/Einstein.pro compiled 0.00 sec, 4,568 bytes
Welcome to SWI-Prolog (Multi-threaded, Version 5.6.14)
Copyright (c) 1990-2006 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
1 ?- owns_zebra(Street, Who).
Street = [house(yellow, norwegian, fox, _G458, kools),
          house(blue, ukrainian, horse, tea, chesterfields),
          house(red, englishman, snails, milk, old_gold),
          house(ivory, spaniard, dog, orange_juice, lucky_strike),
          house(green, japanese, zebra, coffee, parliaments)]
Who = japanese 
Yes
2 ?- 

The beverage in the first house's resident is not shown because there are no information about it. Some variants of the Zebra Puzzle ask "who drinks water?" In this case, it is self-evident that the Norwegian drinks water since every person drinks different beverages.

External links

• Zebra Puzzle in wikipedia
• Another SWI-Prolog solution

Download code