Constraint Satisfaction Problem
As originally defined in artificial intelligence, constraints enumerate the possible values a set of variables may take. Informally, a finite domain is a finite set of arbitrary elements. A constraint satisfaction problem on such domain contains a set of variables whose values can only be taken from the domain, and a set of constraints, each constraint specifying the allowed values for a group of variables. A solution to this problem is an evaluation of the variables that satisfies all constraints. In other words, a solution is a way for assigning a value to each variable in such a way that all constraints are satisfied by these values.
In some circumstances, there may exist additional requirements: one may be interested not only in the solution (and in the fastest or most computationally efficient way to reach it) but in how it was reached; e.g. one may want the "simplest" solution ("simplest" in a logical, non computational sense that has to be precisely defined). This is often the case in logic games such as Sudoku.
In practice, constraints are often expressed in compact form, rather than enumerating all values of the variables that would satisfy the constraint. One of the most used constraints is the one establishing that the values of the affected variables must be all different.
Problems that can be expressed as constraint satisfaction problems are the Eight queens puzzle, the Sudoku solving problem, the Boolean satisfiability problem, scheduling problems and various problems on graphs such as the graph coloring problem.
While usually not included in the above definition of a constraint satisfaction problem, arithmetic equations and inequalities bound the values of the variables they contain and can therefore be considered a form of constraints. Their domain is the set of numbers (either integer, rational, or real), which is infinite: therefore, the relations of these constraints may be infinite as well; for example, has an infinite number of pairs of satisfying values. Arithmetic equations and inequalities are often not considered within the definition of a "constraint satisfaction problem", which is limited to finite domains. They are however used often in constraint programming.
Read more about this topic: Constraint Satisfaction
Famous quotes containing the words constraint, satisfaction and/or problem:
“In America a woman loses her independence for ever in the bonds of matrimony. While there is less constraint on girls there than anywhere else, a wife submits to stricter obligations. For the former, her father’s house is a home of freedom and pleasure; for the latter, her husband’s is almost a cloister.”
—Alexis de Tocqueville (1805–1859)
“It is remarkable with what pure satisfaction the traveler in these woods will reach his camping-ground on the eve of a tempestuous night like this, as if he had got to his inn, and, rolling himself in his blanket, stretch himself on his six-feet-by-two bed of dripping fir twigs, with a thin sheet of cotton for roof, snug as a meadow-mouse in its nest.”
—Henry David Thoreau (1817–1862)
“The thinking person has the strange characteristic to like to create a fantasy in the place of the unsolved problem, a fantasy that stays with the person even when the problem has been solved and truth made its appearance.”
—Johann Wolfgang Von Goethe (1749–1832)