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 problems, 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, 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). Solving Constraint satisfaction problems on finite domains are typically solved using a form of search. The most used techniques are variants of backtracking, constraint propagation, and 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 problems in which the