Information Technology Reference
In-Depth Information
Given the amount of searching and backtracking required to properly place queens
on even an
8
×
8
board, computer scientists have looked for more efficient ways of
solving this problem. One method that works well involves placing the queens ran-
domly on a board and then repeatedly moving one of the queens to reduce its conflicts
with the others.
5.5 A fourth example: Logic problems
This section considers a very different sort of puzzle, often called a
logic problem
,
although it is no more connected to logic than the others. It is a word problem involv-
ing several clues about the identities of individuals playing certain roles. A simple
example illustrates the form:
In conversation, Sandy, Chris, and Pat discovered that they had distinct occupa-
tions and also played distinct musical instruments. Their occupations are doctor,
lawyer, and engineer, and the instruments they play are piano, flute, and violin.
Also,
1.
Chris is married to the doctor.
2.
The lawyer plays the piano.
3.
Chris is not the engineer.
4.
Sandy is a patient of the violinist.
Who plays the flute?
To solve logic puzzles like these as constraint satisfaction problems, one needs to
determine what the variables are, what the domains should be, and how the given
information leads to constraints on the desired solution.
For this example, to determine who plays the flute, it is necessary to figure out
who (among Sandy, Chris, and Pat) plays what instrument and has what job. So the
problem can be characterized as follows:
Variables:
Doctor
,
Lawyer
,
Engineer
,
Piano
,
Violin
,
Flute
Domain:
{
sandy
,
chris
,
pat
}
To
encode
the
given
information
as
constraints,
these
two
implicit
facts
must
somehow be included:
If
x
is married to
y
, then
x
=
y
.
If
x
is a patient of
y
, then
x
=
y
and
y
is the doctor.
