Editing Constraint satisfaction (section)

==Constraint satisfaction problem==
{{main|Constraint satisfaction problem}}

As originally defined in artificial intelligence, constraints enumerate the possible values a set of variables may take in a given world. A [[possible world]] is a total assignment of values to variables representing a way the world (real or imaginary) could be.<ref>{{Cite web | url=https://artint.info/2e/html/ArtInt2e.Ch4.S1.SS1.html | title=4.1.1 Variables and Worlds‣ 4.1 Possible Worlds, Variables, and Constraints ‣ Chapter 4 Reasoning with Constraints ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition | access-date=2018-11-29 | archive-date=2018-11-29 | archive-url=https://web.archive.org/web/20181129100131/https://artint.info/2e/html/ArtInt2e.Ch4.S1.SS1.html | url-status=live }}</ref> 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 the values of the variables that would satisfy the constraint. One  of the most-used constraints is the (obvious) 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 and many other logic puzzles, the [[Boolean satisfiability problem]], [[Scheduling (production processes)|scheduling]] problems, [[interval propagation|bounded-error estimation]] 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, <math>X=Y+1</math> 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]].

It can be shown that the arithmetic inequalities or equations present in some types of finite logic puzzles such as [[Futoshiki]] or [[Kakuro]] (also known as Cross Sums) can be dealt with as non-arithmetic constraints (see ''Pattern-Based Constraint Satisfaction and Logic Puzzles''<ref name="Pattern-Based Constraint Satisfaction and Logic Puzzles">{{in lang|en}} {{cite news | first = Denis | last = Berthier | title = Pattern-Based Constraint Satisfaction and Logic Puzzles | url = http://www.carva.org/denis.berthier/PBCS | archive-url = https://archive.today/20130112121944/http://www.carva.org/denis.berthier/PBCS | url-status = dead | archive-date = 12 January 2013 | work = Lulu Publishers | isbn = 978-1-291-20339-4 | date = 20 November 2012 | accessdate = 24 October 2012 }}</ref>).

===Solving===

Constraint satisfaction problems on finite domains are typically solved using a form of [[Search algorithm|search]]. The most-used techniques are variants of [[backtracking]], [[constraint propagation]], and [[Local search (optimization)|local search]]. These techniques are used on problems with [[nonlinear]] constraints.

[[Variable elimination]] and the [[simplex algorithm]] are used for solving [[linear]] and [[polynomial]] equations and inequalities, and problems containing variables with infinite domain. These are typically solved as [[Optimization (mathematics)|optimization]] problems in which the optimized function is the number of violated constraints.

===Complexity===
{{main|Complexity of constraint satisfaction}}

Solving a constraint satisfaction problem on a finite domain is an [[NP-complete]] problem with respect to the domain size. Research has shown a number of [[Tractable problem|tractable]] subcases, some limiting the allowed constraint relations, some requiring the scopes of constraints to form a tree, possibly in a reformulated version of the problem. Research has also established relationships of the constraint satisfaction problem with problems in other areas such as [[finite model theory]].