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.