Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. The entities in a problem are represented as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of 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 seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems. Examples of problems that can be modeled as a constraint satisfaction problem include:
- Type inference
- N-queens
- Map coloring
- Maximum cut problem
- Sudoku, Crosswords, and many other logic puzzles
Provides two versions of the Crosswords puzzle, both of which are made from scratch. The first is formulated as a CSP and uses constraint programming. The other is a normal version. Made this during my sophomore year :)