Editing Constraint satisfaction (section)

In [[artificial intelligence]] and [[operations research]], '''constraint satisfaction''' is the process of finding a solution through 
a set of [[Constraint (mathematics)|constraint]]s that impose conditions that the [[Variable (mathematics)|variables]] must [[satisfiability|satisfy]].<ref name="Tsang2014">{{cite book|first=Edward|last=Tsang|title=Foundations of Constraint Satisfaction: The Classic Text|url=https://books.google.com/books?id=UFmRAwAAQBAJ|date=13 May 2014|publisher=BoD – Books on Demand|isbn=978-3-7357-2366-6|access-date=25 August 2018|archive-date=6 October 2024|archive-url=https://web.archive.org/web/20241006110429/https://books.google.com/books?id=UFmRAwAAQBAJ|url-status=live}}</ref>  A solution is therefore an assignment of values to the variables that satisfies all constraints&mdash;that is, a point in the [[feasible region]].

The techniques used in constraint satisfaction depend on the kind of constraints being considered. Often used are [[Finite domain constraint|constraints on a finite domain]], to the point that [[constraint satisfaction problem]]s are typically identified with problems based on constraints on a finite domain. Such problems are usually solved via [[Search algorithm|search]], in particular a form of [[backtracking]] or [[local search (constraint satisfaction)|local search]]. [[Constraint propagation]] is another family of methods used on such problems; most of them are incomplete in general, that is, they may solve the problem or prove it unsatisfiable, but not always. Constraint propagation methods are also used in conjunction with search to make a given problem simpler to solve. Other considered kinds of constraints are on [[real number|real]] or [[rational number|rational]] numbers; solving problems on these constraints is done via [[variable elimination]] or the [[simplex algorithm]].

Constraint satisfaction as a general problem originated in the field of [[artificial intelligence]] in the 1970s (see for example {{Harv|Laurière|1978}}). However, when the constraints are expressed as multivariate [[linear equation]]s defining (in)equalities, the field goes back to [[Joseph Fourier]] in the 19th century: [[George Dantzig]]'s invention of the [[simplex algorithm]] for [[linear programming]] (a special case of mathematical optimization) in 1946 has allowed determining feasible solutions to problems containing hundreds of variables.

During the 1980s and 1990s, embedding of constraints into a [[programming language]] was developed. The first language devised expressly with intrinsic support for [[constraint programming]] was [[Prolog]]. Since then, constraint-programming libraries have become available in other languages, such as  [[C++]] or [[Java (programming language)|Java]] (e.g., Choco for Java<ref>Choco: An Open-Source java library for constraint programming. https://choco-solver.org  Accessed Dec 12, 2021.</ref>).