Information Technology Reference
In-Depth Information
5
Case Study: Satisfying Constraints
This chapter returns to the central conjecture of the topic, namely, that ordinary
thinking can be viewed as a form of computation.
One of the difficulties in observing and analyzing our own thinking is that so
much of it happens so quickly that it is hard to describe exactly what takes place. An
example is resolving the pronoun it in the trophy-suitcase sentences in chapter 1. But
not all thinking is like this, fortunately. Consider working on a puzzle that appears
in a newspaper. There, the reasoning can go on for minutes, even hours. This is
the sort of thinking that is the subject matter of this chapter. The thinking needed
to solve a wide variety of reasoning puzzles can be formulated in the same way, in
terms of constraint satisfaction problems . This chapter describes five different constraint
satisfaction problems. (Chapter 6 shows that some parts of visual interpretation can
also be formulated in this way.)
The approach to constraint satisfaction problems here is not that of an expert but
more of a novice, with considerable trial-and-error and guesswork involved. The Pro-
log programs presented in this chapter work well enough for the easiest forms of
the puzzles but will gradually stop working as the puzzles get harder. (What makes
a puzzle hard is one of the issues to be discussed.) Some time is spent trying to
do better than guessing, but this is not the main focus. Finding ways to cope with
challenging puzzles as an expert would is a whole area of research in itself (called
constraint programming) that is beyond the scope of this topic.
In working through various examples of constraint satisfaction problems, new fea-
tures of Prolog are introduced as needed, for example, producing output (to display
helpful messages), anonymous variables (to avoid having to give names to variables),
and numbers (to do arithmetic in Prolog).
The first section of this chapter introduces the idea of constraint satisfaction prob-
lems and presents a general way of solving them. Each of the five remaining sections
takes on a different constraint satisfaction problem (Sudoku, cryptarithmetic, the
 
 
Search WWH ::




Custom Search