Navigation  without Java Scripts

The Zebra Problem

Using Prolog's list handling capabilities to solve the Zebra problem

Another very good example of Prolog's general purpose problem solving capabilities as well as its list-handling-facilities is the Zebra program.

The problem is a classic constraint-resolution problem. In 5 houses, each with a different color, live 5 persons of different nationalities, who each prefer different brands of cigarettes, drinks, pets etc. To start with You are given a number of facts and a question like "Who lives in the house to the left of the man that has a pet zebra ?".

Have a look at the program and see how elegant the Prolog solution is. Everything, including the constraints, is represented as lists (e.g. "in the 3rd house they smoke cigars").

To help solve the puzzle a small toolbox of list-handling predicates has been created. These tools solve the problem. Note that it is a general-purpose program that can easily be adapted to similar kinds of problems.

A PROLOG program to solve the "5 houses" problem using a "verify and choose" method. A candidate solution is any of the (5!)**5 ways of distributing 5 colours, 5 drinks, 5 nationalities, 5 cigarettes, and 5 pets amongst 5 houses. By Lewis Baxter

There are five houses with five different colours, in each house lives a person of different nationality having favorite drinks, cigarettes and pets, the information is:

The Englishman lives in the Red house.
The Spaniard owns the Dog.
The Norwegian lives in the first house on the left.
Kools are smoked in the Yellow house.
The man who smokes Chesterfields lives in the house next to the man with the Fox.
The Norwegian lives next to the Blue house.
The Winston smoker owns Snails.
The Lucky Strike smoker drinks orange juice.
The Ukrainian drinks tea.
The Japanese smokes Parliaments.
Kools are smoked in the house next to the house where the Horse is kept.
Coffee is drunk in the Green house.
The Green house is immediately to the right (your right) of the Ivory house.
Milk is drunk in the middle house.

The question is then: Where does the Zebra live, and in which house do they drink water ?

To execute the program as a CGI script press the "Solve" button below


 

Show Source to the Zebra-application.

Show Source to the Zebra-application incl. cgi-support.