Constraint Satisfaction Problem
Constraint satisfaction problems (CSPs) are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of intense research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. The boolean satisfiability problem (SAT), the Satisfiability Modulo Theories (SMT) and answer set programming (ASP) can be roughly thought of as certain forms of the constraint satisfaction problem.
Examples of simple problems that can be modeled as a constraint satisfaction problem
- Eight queens puzzle
- Map coloring problem
- Sudoku
Examples demonstrating the above are often provided with tutorials of 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.
Read more about Constraint Satisfaction Problem: Formal Definition, Resolution of CSPs, Variants of CSPs
Famous quotes containing the words constraint, satisfaction and/or problem:
“In America a woman loses her independence for ever in the bonds of matrimony. While there is less constraint on girls there than anywhere else, a wife submits to stricter obligations. For the former, her father’s house is a home of freedom and pleasure; for the latter, her husband’s is almost a cloister.”
—Alexis de Tocqueville (1805–1859)
“Besides, our action on each other, good as well as evil, is so incidental and at random, that we can seldom hear the acknowledgments of any person who would thank us for a benefit, without some shame and humiliation. We can rarely strike a direct stroke, but must be content with an oblique one; we seldom have the satisfaction of yielding a direct benefit, which is directly received.”
—Ralph Waldo Emerson (1803–1882)
“The government is huge, stupid, greedy and makes nosy, officious and dangerous intrusions into the smallest corners of life—this much we can stand. But the real problem is that government is boring. We could cure or mitigate the other ills Washington visits on us if we could only bring ourselves to pay attention to Washington itself. But we cannot.”
—P.J. (Patrick Jake)