Editing Constraint satisfaction problem (section)

==Solution==
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 also often combined, as in the [[Very large-scale neighborhood search|VLNS]] method, and current research involves other technologies such as [[linear programming]].<ref>{{Cite conference|title=Hybrid optimization : the ten years of CPAIOR|date=2011|publisher=Springer|editor1=Milano, Michela |editor1-link=Michela Milano |editor2=Van Hentenryck, Pascal |conference=International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems |isbn=9781441916440|location=New York|oclc=695387020}}</ref>

[[Backtracking]] is a recursive algorithm. It maintains a partial assignment of the variables. Initially, all variables are unassigned. At each step, a variable is chosen, and all possible values are assigned to it in turn. For each value, the consistency of the partial assignment with the constraints is checked; in case of consistency, a [[Recursion|recursive]] call is performed. When all values have been tried, the algorithm backtracks. In this basic backtracking algorithm, consistency is defined as the satisfaction of all constraints whose variables are all assigned. Several variants of backtracking exist. [[Backmarking]] improves the efficiency of checking consistency. [[Backjumping]] allows saving part of the search by backtracking "more than one variable" in some cases. [[Constraint learning]] infers and saves new constraints that can be later used to avoid part of the search. [[Look-ahead (backtracking)|Look-ahead]] is also often used in backtracking to attempt to foresee the effects of choosing a variable or a value, thus sometimes determining in advance when a subproblem is satisfiable or unsatisfiable.

[[Constraint propagation]] techniques are methods used to modify a constraint satisfaction problem. More precisely, they are methods that enforce a form of [[local consistency]], which are conditions related to the consistency of a group of variables and/or constraints. Constraint propagation has various uses. First, it turns a problem into one that is equivalent but is usually simpler to solve. Second, it may prove satisfiability or unsatisfiability of problems. This is not guaranteed to happen in general; however, it always happens for some forms of constraint propagation and/or for certain kinds of problems. The most known and used forms of local consistency are [[arc consistency]], [[hyper-arc consistency]], and [[path consistency]]. The most popular constraint propagation method is the [[AC-3 algorithm]], which enforces arc consistency.

[[Local search (optimization)|Local search]] methods are incomplete satisfiability algorithms. They may find a solution of a problem, but they may fail even if the problem is satisfiable. They work by iteratively improving a complete assignment over the variables. At each step, a small number of variables are changed in value, with the overall aim of increasing the number of constraints satisfied by this assignment.  The [[min-conflicts algorithm]] is a local search algorithm specific for CSPs and is based on that principle. In practice, local search appears to work well when these changes are also affected by random choices. An integration of search with local search has been developed, leading to [[Hybrid algorithm (constraint satisfaction)|hybrid algorithms]].