bts (03/19/83)
From: Chris Moss <Moss@UPenn>
Subject: Zebra Puzzle - Clue 2
Date: 18 Mar 1983 21:03-EST
Zebra Problem - Clue #2
There are 14 clues to the problem (15 if you include the question).
What is a clue? It is a constraint on the solution of the problem.
If we look at the clues we discover there are four different types.
The simplest is illustrated by the first clue:
The englishman lives in the red house.
(any ideological overtones here?). This relates two facts about a
particular house, so we may call it a house clue and write it:
houseclue(1, [english, red, _, _, _]).
where we assume that a 5-place list represents
[nationality, color, pet, drink, cigarette].
The clue doesn't tell us anything about the other three characteristics,
so we use the unnamed variable for them.
Another particularly useful type of clue is found in clues 8 and 9.
These tell us facts about particular houses in the row. In representing
these clues we constrain the solution space to contain only 5 houses.
Having done this we can simply represent the solution by a logical
variable and know that it will come out as a 5 by 5 grid.
This should give you a start on setting up the problem in order to find
the answer; but be careful! The search space is enormous: there are
5!^5, or about 25 billion, possible solutions. So don't set your Prolog
going with the most naive search strategy.
More clues to come...
Chris Moss.