Constraint-satisfaction problems or CSPs are mathematical problems where one must find states or objects in a system that satisfy a number of constraints or criteria. CSPs are the subject of intense research in both artificial intelligence and operations research. Many CSPs require a combination of heuristics and combinatorial search methods to solve in a reasonable time. Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations by or about: Mathematics Look up Mathematics in Wiktionary, the free dictionary Wikimedia Commons has more media related to: Mathematics Bogomolny, Alexander: Interactive Mathematics Miscellany and Puzzles. ... A constraint is a limitation of possibilities. ... Artificial intelligence (also known as machine intelligence and often abbreviated as AI) is intelligence exhibited by any manufactured (i. ... Operations research, operational research, or simply OR, is the use of mathematical models, statistics and algorithms to aid in decision-making. ... For heuristics in computer science, see heuristic (computer science) Heuristic is the art and science of discovery and invention. ... Combinatorial search is a branch of computer science that sits at the intersection of several fields, including artificial intelligence, mathematics and software engineering. ...
Examples of algorithms used in constraint-satisfaction problems: One of the 12 unique solutions The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queens moves. ... Example of a four color map The four color theorem states that any plane separated into regions, such as a political map of the counties of a state, can be colored using no more than four colors in such a way that no two adjacent regions receive the same color. ... A Sudoku puzzle (image hyperlinked to solution) Sudoku (Japanese: 数独, sūdoku), sometimes spelled Su Doku, is a placement puzzle, also known as Number Place in the United States. ...
See also: The AC-3 algorithm (short for Arc Consistency Algorithm #3) is one of a series of algorithms used for the solution of constraint satisfaction problems (or CSPs). ... Backtracking is a strategy for finding solutions to constraint satisfaction problems. ... The min conflicts algorithm is a search algorithm to solve constraint satisfaction problems (CSP problems). ...
Declarative programming is an approach to computer programming that involves the creation of a set of conditions that describe a solution space, but leaves the interpretation of the specific steps needed to arrive at that solution up to an unspecified interpreter. ... Constraint programming is a programming paradigm in which a set of constraints that a solution must meet are specified rather than set of steps to obtain such a solution. ...
External links
One very good text on the subject is Edward Tsang's Foundations of Constraint Satisfaction.
Often used are constraints on a finite domain, to the point that constraintsatisfactionproblems are typically identified with problems based on constraints on a finite domain.
Constraint propagation are other 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.
Problems that can be expressed as constraintsatisfactionproblems are the Eight queens puzzle, the Sudoku solving problem, the Boolean satisfiability problem, scheduling problems and various problems on graphs such as the graph coloring problem.
Constraintsatisfactionproblems or CSPs are mathematicalproblems where one must find states or objects that satisfy a number of constraints or criteria.
If such a dichotomy is true, then CSPs provide one of the largest known subsets of NP which avoids problems that are neither polynomial time solvable nor NP-complete, whose existence was demonstrated by Ladner.
Most classes of CSPs that are known to be tractable are those where the hypergraph of constraints has bounded treewidth (and there are no restrictions on the set of constraint relations), or where the constraints have arbitrary form but there exist essentially non-unary polymorphisms of the set of constraint relations.
Feeds |
Contact