bts@unc.UUCP (06/02/83)
Starting with problem #26 in his book "What is the Name
of this Book?", Raymond Smullyan presents a number of varia-
tions on a familiar logic puzzle. Here's his introduction
to the section:
There is a wide variety of puzzles about an island in
which certain inhabitants called "knights" always tell
the truth, and others called "knaves" always lie. It
is assumed that every inhabitant is either a knight or
a knave.
All the puzzles involve meeting a small party of the
island's inhabitants. Sometimes a question must be asked,
other times information is volunteered. In all cases, the
goal is to determine which are knights and which are knaves.
A sample of this type of puzzle is the following:
#31. Again we have three people, A,B,C, each of whom is
either a knight or a knave. A and B make the following
statements:
A: All of us are knaves.
B: Exactly one of us is a knight.
What are A,B,C?
I've played around at solving these puzzles using
Prolog-- with only mixed results. Here's the challenge for
Prolog programmers: Write a Prolog program which will solve
this type of problem, where a problem description is a list
of names (e.g. A,B,C) and statements. Restrict the state-
ments the people may make, but at least let them make claims
about which groups they and their companions belong to.
This simplest puzzle may seem too easy-- the set of
possible solutions is small enough to examine 'em all, for
instance. The puzzles in the book quickly increase in dif-
ficulty, however. One simple variation is introduced in
problem #39, with the addition of "normals", who sometimes
tell the truth and sometimes lie. (By the end of the book,
Smullyan is playing around with Godel's Theorem.) I'd be
interested in seeing how far people can go with knights and
knaves problems (or beyond), comments on solving this type
of puzzle (where the truth or falsity of statements must be
determined before they can be used), etc.
Bruce Smith, UNC-CH
duke!unc!bts (USENET)
bts.unc@udel-relay (other NETworks)