Skip to content

Latest commit

 

History

History
73 lines (48 loc) · 2.37 KB

README.md

File metadata and controls

73 lines (48 loc) · 2.37 KB
Raw

CSP.JS

Constraint Satisfaction Problem Solver

This is a library for expressing and solving constraint satisfaction problems, in pure JavaScript. Currently it only solves discrete finite-domain problems, and provides a couple of solvers. In the future I hope to support infinite-domain problems and continuous problems as well.

Example

var p = csp.DiscreteProblem();

p.addVariable("a", [1,2,3]);
p.addVariable("b", [4,5,6]);
p.addVariable("c", [6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]);

p.addConstraint(
	["a", "b"],
	function(a, b) { return a*2 === b; }
);

p.addConstraint(
	["b", "c"],
	function(b, c) { return b*2 === c; }
);

var one_solution = p.getSolution();
var all_solutions = p.getSolutions();

Solvers and Problems we support

Currently we support finite-domain problems, with the following solvers:

  • Recursive Backtracking
  • Forward-Checking (in progress)
  • AC3 Arc Consistency (in progress)

Intro to CSPs

What is a CSP?

A Constraint Satisfaction Problem is formally defined as:

  • A set of variables, Xi ... Xn
  • Each variable has a domain of values it can take, Di ... Dn
  • A set of constraints Ci ... Cn that specifies allowable combinations of values for a subset of the variables.

That is, a set of variables, with relations between the valid values of these variables.

There are multiple classes of CSPs:

  • Discrete problems, where the values of each variable can be enumerated
  • Finite problems, where the size of domain is finite
  • Continuous problems, where the values of each variable is a range
  • Infinite problems, where the domain of a variable is of infinite extent

Then there are subclasses of these:

  • Integer problems, discrete infinite problems on the integers
  • Binary constraint problems, where all the constraints are between two variables
  • Linear problems, where all the constraints are linear
  • Integer Linear problems, where all the constraints are linear and the values integers. This is the hardest kind of constraint problem.
  • And many more...

Examples of real-world CSPs

There are tons and tons of problems that can reduce to constraint satisfaction problems, and it is a rich field of study. But, here's some that everyone knows about:

  • Sudoku
  • Coloring maps
  • Scheduling blocks of time

Credits

This project started as a port of the python-constraint library