Information Technology Reference
In-Depth Information
[26] first formulated constraint satisfaction problems in the form considered here.
They also proposed methods of solving them that appear to work much better in
practice than generate-and-test. An excellent graduate-level textbook about this area
of research is by Dechter [24]. (Note: Scheduling has a history of its own outside of
computer science in the area of operations research.)
Constraint satisfaction is connected to many areas of computer science, for example,
answering queries in databases [28]. As it turns out, it also raises a very fundamental
question about computation itself. To take Sudoku as an example, each Sudoku puzzle
is of size
n
2
n
2
121), and the search space grows very
quickly, in fact, exponentially with
n
. The question is whether there is a way to solve
these puzzles that is
guaranteed
to do better than generate-and-test over this enormous
space.
This question can be reformulated in a mathematically precise way using the notion
of a Turing machine (mentioned at the end of chapter 1). Is there a Turing machine
M
and a polynomial
P
such that
M
can solve any Sudoku puzzle of size
n
2
×
for some
n
(like 9
×
9 or 121
×
n
2
(or report
×
(
)
that there is no solution) in no more than
P
steps? The answer, remarkably enough,
is that nobody knows. The question is equivalent to the famous
P
=
NP
question, first
posed by Stephen Cook [23] in the 1970s, and despite the best efforts of thousands
of computer scientists and mathematicians since then, it has remained unanswered.
Anyone who can answer it will become instantly famous and receive a $1 million
reward from the Clay Mathematics Institute. What
is
known about the question is
that no matter how the answer turns out, it will affect the view of thousands of other
computational tasks, some of which have direct economic significance [25].
n
Exercises
1.
This chapter presented three different ways of handling equality in Prolog:
=
,
=:=
, and
is
. For each of the three, explain briefly what its purpose is, and
present an example setting where it should be used but where the other two
should not be used.
2.
Draw a map of central Europe consisting of the following seven countries: France,
Switzerland, Italy, Belgium, Holland, Germany, and Austria. Color the countries
on the map using just red, yellow, and orange; no two countries with a border
between them can be the same color. Look at an existing map to see where the
borders are, and then write a Prolog program that will find a color for each
country.
