Constraint
Satisfaction Problem
Constraint
satisfaction problems or CSPs are mathematical problems
where one must
find states or
objects that satisfy a number of constraints or criteria. A constraint
is a
restriction of the
feasible solutions in an optimization problem.
Many problems can be
stated as constraints satisfaction problems. Here are some
examples:
Example
1: The n-Queen problem is the problem of putting n chess queens
on an n×n
chessboard such that
none of them is able to capture any other using the standard chess
queen's moves. The
colour of the queens is meaningless in this puzzle, and any queen is
assumed to be able to
attack any other. Thus, a solution requires that no two queens share
the same row, column,
or diagonal.
The problem was
originally proposed in 1848 by the chess player Max Bazzel, and over
the years, many
mathematicians, including Gauss have worked on this puzzle. In 1874, S.
Gunther proposed a
method of finding solutions by using determinants, and J.W.L.
Glaisher refined this
approach.
The eight queens
puzzle has 92 distinct solutions. If solutions that differ only by
symmetry operations
(rotations and reflections) of the board are counted as one, the
puzzle has 12 unique
solutions. The following table gives the number of solutions for n
queens, both unique
and distinct.
A Constraint Satisfaction
Problem (CSP) is characterized by:
• a set of variables {x1,
x2, .., xn},
• for each variable xi a domain
Di with the possible values for that variable, and
• a set of constraints,
i.e. relations, that are assumed to hold between the values of
the variables. [These relations
can be given intentionally, i.e. as a formula, or
extensionally, i.e. as a set, or
procedurally, i.e. with an appropriate generating or
recognising function.] We will
only consider constraints involving one or two
variables.
The constraint
satisfaction problem is to find, for each i from 1 to n, a value in Di for xi
so that all constraints are
satisfied.
Backtracking
Search and Local search for CSP
Backtracking
We
order the variables in some fashion, trying to place first the variables that
are more
highly constrained or
with smaller ranges. This order has a great impact on the efficiency
of solution
algorithms and is examined elsewhere. We start assigning values to variables.
We
check constraint satisfaction at the earliest possible time and extend an
assignment if
the constraints
involving the currently bound variables are satisfied.
Example
2 Revisited: In our crossword puzzle we may order the variables as follows:
1ACROSS, 2DOWN,
3DOWN, 4ACROSS, 7ACROSS, 5DOWN, 8ACROSS, 6DOWN.
Heuristic Search (Local Search) in CSP
In the last few
years, greedy local search strategies became popular, again. These
algorithms
incrementally alter inconsistent value assignments to all the variables. They
use a
"repair" or "hill climbing" metaphor to move towards more
and more complete
solutions. To avoid
getting stuck at "local optima" they are equipped with various
heuristics for
randomizing the search. Their stochastic nature generally voids the
guarantee of
"completeness" provided by the systematic search methods.
The local search
methodology uses the following terms:
• state
(configuration): one possible assignment of all variables; the number of
states is equal to
the product of domains' sizes
• evaluation
value: the number of constraint violations of the state (sometimes
weighted)
• neighbor: the
state which is obtained from the current state by changing one
variable value
• local-minimum: the
state that is not a solution and the evaluation values of all of
its neighbors are
larger than or equal to the evaluation value of this state
• strict
local-minimum: the state that is not a solution and the evaluation values
of
all of its neighbors
are larger than the evaluation value of this state
• non-strict
local-minimum: the state that is a local-minimum but not a strict
local-minimum.
