Constraint satisfaction problem

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose <a href="/facts/State_(computer_science)/4Yu8xXHS">state</a> must satisfy a number of <a href="/facts/Constraint_(mathematics)/QLFIFlFX">constraints</a> or <a href="/facts/Limit_(mathematics)/j8JBhj4e">limitations</a>. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over <a href="/facts/Variable_(mathematics)/VbQlrvKz">variables</a>, which is solved by <a href="/facts/Constraint_satisfaction/PXI74p1T">constraint satisfaction</a> methods. CSPs are the subject of research in both <a href="/facts/Artificial_intelligence/lJGauQwX">artificial intelligence</a> and <a href="/facts/Operations_research/H5yJkV5n">operations research</a>, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. <a href="/facts/Complexity_of_constraint_satisfaction/y6MyoQQK">CSPs often exhibit high complexity</a>, requiring a combination of <a href="/facts/Heuristics/BcBEkv9c">heuristics</a> and <a href="/facts/Combinatorial_search/tvVPT1pt">combinatorial search</a> methods to be solved in a reasonable time. <a href="/facts/Constraint_programming/rgkCK5bD">Constraint programming</a> (CP) is the field of research that specifically focuses on tackling these kinds of problems. Additionally, the <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">Boolean satisfiability problem</a> (SAT), <a href="/facts/Satisfiability_modulo_theories/10mBFLFB">satisfiability modulo theories</a> (SMT), <a href="/facts/Mixed_integer_programming/GduXFQxT">mixed integer programming</a> (MIP) and <a href="/facts/Answer_set_programming/Qv1BmBWU">answer set programming</a> (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.
Examples of problems that can be modeled as a constraint satisfaction problem include:

<ul><li><a href="/facts/Type_inference/vX9K8Qhf">Type inference</a></li>
<li><a href="/facts/Eight_queens_puzzle/XDx2HwlB">Eight queens puzzle</a></li>
<li><a href="/facts/Graph_coloring/J6HoBfP0">Map coloring problem</a></li>
<li><a href="/facts/Maximum_cut/9rulcdeW">Maximum cut problem</a></li>
<li><a href="/facts/Sudoku/I5Savmhf">Sudoku</a>, <a href="/facts/Crossword/dVE9t0pL">crosswords</a>, <a href="/facts/Futoshiki/wXzC0Mrq">futoshiki</a>, <a href="/facts/Kakuro/jNkWlllU">Kakuro</a> (Cross Sums), <a href="/facts/Numbrix/leGzboys">Numbrix</a>/<a href="/facts/Hidato/leGzboys">Hidato</a>, <a href="/facts/Zebra_Puzzle/QRYUWByB">Zebra Puzzle</a>, and many other <a href="/facts/Logic_puzzle/Q1LLT6TR">logic puzzles</a></li></ul>
These are often provided with tutorials of <a href="/facts/Constraint_programming/rgkCK5bD">CP</a>, ASP, Boolean SAT and SMT solvers. In the general case, constraint problems can be much harder, and may not be expressible in some of these simpler systems. "Real life" examples include <a href="/facts/Automated_planning/VL1TcrmD">automated planning</a>, <a href="/facts/Lexical_disambiguation/Mfcw7gsu">lexical disambiguation</a>, <a href="/facts/Musicology/jaapApYh">musicology</a>, <a href="/facts/Configure%2c_price_and_quote/RBpdCz4l">product configuration</a> and <a href="/facts/Resource_allocation/QmQWt2Yg">resource allocation</a>.
The existence of a solution to a CSP can be viewed as a <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a>. This can be decided by finding a solution, or failing to find a solution after exhaustive search (<a href="/facts/Stochastic_algorithm/uMbgL94r">stochastic algorithms</a> typically never reach an exhaustive conclusion, while directed searches often do, on sufficiently small problems). In some cases the CSP might be known to have solutions beforehand, through some other mathematical inference process.

Constraint satisfaction problem open-in-new

Constraint satisfaction problem