Constraint satisfaction problems (CSPs) are mathematical questions 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.
This website serves as a host to a collection of interactive CSP solvers, each of which is designed to solve a specific type of CSP. The solvers are implemented in TypeScript and are available for use in the browser. The source code is available on GitHub.
Take a look!
Formally, a CSP is a defined as a triple \( \langle X, D, C \rangle \), where
- \( X = \{ x_1, \dots, x_n \} \) is a set of variables,
- \( D = \{ D_1, \dots, D_n \} \) is a set of domains, and
- \( C = \{ C_1, \dots, C_m \} \) is a set of constraints.
The assignments of the variables \( x_1, \dots, x_n \) must always be contained in their respective domain, \( x_i \in D_i \). An evaluation \( u \) assigns a subset of the variables \( X \) to specific values in their respective domains. Such an evaluation is said to be consistent if the assigned values satisfy all constraints associated with their variables. It is called complete if all variables have an assigned value. An evaluation that is both consistent and complete is called a solution.
The solver on this site uses a recursive backtracking strategy to find such a solution. For some puzzles this process can be optimized by explicit restrictions on the domains and faster constraint checks.