Information Technology Reference
In-Depth Information
5.1.2 Variables, domains, constraints
Map coloring is a very simple example of a
constraint satisfaction problem
. In general,
these are made up of the following three components:
There are some number of
variables
for which values are to be found. In the
case of map coloring, the variables
A
,
B
,
C
,
D
,
E
represent the colors of the five
countries.
Each variable gets a value from some finite
domain
of values. In the case of map
coloring, each variable has the same domain: the colors red, white, and blue.
There are
constraints
to be satisfied among subsets of the variables. In the case
of map coloring, the constraints are that the colors of countries with borders
between them must be different.
A
solution
to a constraint satisfaction problem is an assignment of a value to each
variable (taken from the domain of the variable) such that all the constraints are
satisfied. In other words, solving a constraint satisfaction problem means finding
values for the variables subject to the constraints.
The simplest way to solve a constraint satisfaction problem in Prolog is to use
generate-and-test: generate values from the domain for each variable, and then test to
see if all the constraints are satisfied, backtracking as necessary.
A Prolog program that solves an arbitrary constraint satisfaction problem using
generate-and-test can be constructed using a format somewhat like the following:
solution(
Variable
1
,
Variable
2
,. . .,
Variable
n
):-
domain
1
(
Variable
1
),
...
domain
n
(
Variable
n
),
constraint
1
(
Variable
,
...
,
Variable
),
...
constraint
m
(
Variable
, ...,
Variable
).
This is the form used for the map coloring.
5.1.3 Output in Prolog
When a Prolog query succeeds, it displays values for all the variables. To make the
answer easier to read, however, it is often useful to display more. Prolog provides two
special predicates that can be used for this in queries or in the bodies of clauses:
