Visualize solving constraint satisfaction problems.
This project is maintained by PrajitR
Constraint satisfaction problems (CSPs) are problems where you solve for the values of a set of variables, subject to some constraints.
Take map coloring. Each state in the US map can take on one of four colors. However, neighboring states cannot have the same color. If California is red, Oregon cannot also be red. In this CSP, the US states are the set of variables, their domains are the four colors, and the constraints are the neighbor color restrictions.
Another example of a CSP is Sudoku. Each square in the 9x9 grid can take on values from 1 to 9 inclusive. However, squares in the same row, same column, or same 3x3 block cannot take on that value. For example, if the square at position (2, 7) has a value of 4, other squares in row 2, column 7, and block 3 (third block in the first block row) cannot be 4. The 81 squares are the set of variables, their domains are numbers from 1 to 9, and the constraints are the row/column/block restrictions.
Yet another CSP is the N-Queens problem. Each of N queens can be on any square of a NxN board. However, no queen should be able to kill another queen based on the rules of chess. That is, if you place a queen on a particular square, no other queen can be on the same row, same column, or same diagonals; otherwise, the queens could kill each other. In this CSP, the queens are the set of variables, their domains are the squares on the board, and the constraints are the killing restrictions.
csp.js can solve all these problems and provide hooks to visualize the solving process. Usage of the library is described in the main project's README.
Coloring the 50 US states without neighboring states having the same color:
var us = {}, variables = {}, constraints = [],
neighbors = {"WA": ["ID", "OR"], ... }; // The full JSON file at https://gist.github.com/PrajitR/0afccfa4dc4febe59276
function neq(c1, c2) { return c1 != c2; } // Colors of two neigboring states cannot be equal.
for (var state in neighbors) {
variables[state] = ["red", "blue", "green", "yellow"]; // Domains of each state.
for (var i = 0, s = neighbors[state]; i < s.length; i++) {
constraints.push([state, s[i], neq]); // Constraint for each state.
}
}
function visualize(assigned) {
for (var state in assigned) {
$("#" + state).css("fill", assigned[state][0]);
}
}
us.variables = variables;
us.constraints = constraints;
us.cb = visualize;
us.timeStep = 500; // 500ms between updates.
var result = csp.solve(us);
N-Queens problem with board size N = 12. We restrict each queen to only one column instead of all squares. Though restricted, this is the same problem, but computation is a significantly faster.
var SIZE = 12, board = {}, variables = {}, constraints = [];
function not_colliding(i, j) {
function diagonal(a, b) {
return Math.abs(a[0] - b[0]) == Math.abs(a[1] - b[1]);
}
// Row || Column || Diagonal constraints.
return !(i[0] == j[0] || i[1] == j[1] || diagonal(i, j));
}
for (var i = 0; i < SIZE; i++) {
var queenPos = [];
for (var j = 0; j < SIZE; j++) {
queenPos.push([i, j]); // Domain of squares in column i.
if (i != j) { constraints.push([i, j, not_colliding]); } // The queens in columns i and j.
}
variables[i] = queenPos;
}
// You can skip over the visualization function - it's just a bunch of hacky text mangling.
var node = $('#nqueens');
function visualize(assigned) {
var text = '', divider = '';
for (var i = 0; i < SIZE * 6 + 1; i++) { divider += '-'; }
text += divider + '\n';
for (var i = 0; i < SIZE; i++) {
for (var j = 0; j < SIZE; j++) {
text += '|';
var mid = assigned[j] && assigned[j][0][1] == i ? j : ' ';
text += ' ' + mid + ' ';
}
text += '|\n' + divider + '\n';
}
node.html(text);
}
board.variables = variables;
board.constraints = constraints;
board.cb = visualize;
board.timeStep = 500;
csp.solve(board);
The board on the left/top is the starting board. The board on the right/bottom is getting solved.
var SIZE = 9, BLOCK_SIZE = Math.sqrt(SIZE) | 0, domain = [],
sudoku = {}, variables = {}, constraints = [],
filled_in = {};
// Filled in values.
var evil = [ [[1, 1], 6], [[1, 5], 2], [[1, 6], 5], [[1, 7], 8],
[[2, 5], 7], [[3, 1], 8], [[3, 3], 4], [[3, 9], 9],
[[4, 1], 4], [[4, 3], 7], [[4, 4], 3], [[4, 8], 2],
[[5, 2], 1], [[5, 8], 9], [[6, 2], 8], [[6, 6], 4],
[[6, 7], 5], [[6, 9], 7], [[7, 1], 3], [[7, 7], 7],
[[7, 9], 2], [[8, 5], 9], [[9, 3], 2], [[9, 4], 5],
[[9, 5], 6], [[9, 9], 1] ];
evil.forEach(function (x) { filled_in[x[0]] = x[1]; });
for (var i = 1; i <= SIZE; i++) { domain.push(i); } // Range from 1 to 9.
function neq(x, y) { return x != y; }
for (var i = 1; i <= SIZE; i++) {
for (var j = 1; j <= SIZE; j++) {
var fi = filled_in[[i,j]];
variables[[i, j]] = fi ? [fi] : domain.slice(); // If filled in, 1-number domain. Otherwise, 9-number domain.
// Vertical and horizontal constraints.
for (var k = 1; k <= SIZE; k++) {
if (neq(i, j)) {
constraints.push([[i, k], [j, k], neq]);
constraints.push([[k, i], [k, j], neq]);
}
}
// Block constraints (smells like a hack).
var v = (i - 1) / BLOCK_SIZE | 0, h = (j - 1) / BLOCK_SIZE | 0;
for (var k = v * 3; k < (v + 1) * BLOCK_SIZE; k++) {
for (var m = h * 3; m < (h + 1) * BLOCK_SIZE; m++) {
if (neq(i, k + 1) || neq(j, m + 1)) {
constraints.push([[k + 1, m + 1], [i, j], neq]);
}
}
}
}
}
// Braces hell. Sorry.
// Again, you can ignore the ugly visualization code.
var node = $('#sudoku');
function visualize(assigned) {
var text = '', divider = '';
for (var i = 0; i <= SIZE * 4 - 1; i++) { divider += '-'; }
text += divider + '\n';
for (var i = 1; i <= SIZE; i++) {
var row = '|';
for (var j = 1; j <= SIZE; j++) {
row += assigned[[i, j]] || ' ';
row += j % BLOCK_SIZE != 0 ? ' ' : ' | '; // block boundaries.
}
text += row + '\n';
if (i % BLOCK_SIZE == 0) { text += divider + '\n'; }
}
node.html(text);
return text;
}
sudoku.variables = variables;
sudoku.constraints = constraints;
sudoku.cb = visualize;
sudoku.timeStep = 500;
var result = csp.solve(sudoku);