From 47cb23ce1f991c21ceb9273cf4bed717a09abd9a Mon Sep 17 00:00:00 2001 From: erdgeist Date: Mon, 26 May 2025 15:55:29 +0200 Subject: Kickoff commit --- csp.js | 181 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 181 insertions(+) create mode 100644 csp.js (limited to 'csp.js') diff --git a/csp.js b/csp.js new file mode 100644 index 0000000..139b70d --- /dev/null +++ b/csp.js @@ -0,0 +1,181 @@ +!function() { + +var CSP = {}, + FAILURE = 'FAILURE', + stepCounter = 0; + +CSP.solve = function solve(csp) { + // Solves a constraint satisfaction problem. + // `csp` is an object that should have the properties: + // `variables` : object that holds variable names and their domain. + // `constraints`: list of constraints where each element is an + // array of [head node, tail node, constraint function] + // `cb`: callback function for visualizing assignments. It is passed in + // an "assigned" object, an "unassigned" object, and `csp`. + // `timeStep`: milliseconds between invocations of `cb`. + + csp.timeStep = csp.timeStep || 1; + var result = backtrack({}, csp.variables, csp); + if (result == FAILURE) { return result; } + // Unwrap values from array containers. + for (var key in result) { + result[key] = result[key][0]; + } + return result; +} + +function backtrack(_assigned, unassigned, csp) { + // Backtracking search. + + // Copying assigned in necessary because we modify it. Without copying + // the object over, modifying assigned would also change values for old + // assigned objects (which are used in callbacks). + var assigned = {}; + for (var key in _assigned) { assigned[key] = _assigned[key]; } + + if (finished(unassigned)) { return assigned; } // Base case. + var nextKey = selectUnassignedVariable(unassigned), + values = orderValues(nextKey, assigned, unassigned, csp); + delete unassigned[nextKey]; + + for (var i = 0; i < values.length; i++) { + stepCounter++; + assigned[nextKey] = [values[i]]; // Assign a value to a variable. + var consistent = enforceConsistency(assigned, unassigned, csp); + var newUnassigned = {}, newAssigned = {}; + for (var key in consistent) { + if (assigned[key]) { newAssigned[key] = assigned[key].slice(); } + else { newUnassigned[key] = consistent[key].slice(); } + } + if (csp.cb) { + setTimeout( + // Need a closure to fix values of newAssigned and newUnassigned. + // Otherwise, _every_ call of the callback takes the on values of the last iteration. + (function (newAssigned, newUnassigned) { + return function () { csp.cb(newAssigned, newUnassigned, csp); }; + })(newAssigned, newUnassigned), + stepCounter * csp.timeStep + ); + } + if (anyEmpty(consistent)) { continue; } // Empty domains means failure. + var result = backtrack(newAssigned, newUnassigned, csp); + if (result != FAILURE) { return result; } + } + + return FAILURE; +} + +function finished(unassigned) { + // Checks if there are no more variables to assign. + return Object.keys(unassigned).length == 0; +} + +function anyEmpty(consistent) { + // Checks if any variable's domain is empty. + for (var key in consistent) { + if (consistent[key].length == 0) { return true; } + } + return false; +} + +function partialAssignment(assigned, unassigned) { + // Combine unassigned and assigned for use in enforceConsistency. + var partial = {}; + for (var key in unassigned) { partial[key] = unassigned[key].slice(); } + for (var key in assigned) { partial[key] = assigned[key].slice(); } + return partial; +} + +function enforceConsistency(assigned, unassigned, csp) { + // Enforces arc consistency by removing inconsistent values from + // every constraint's tail node. + + function removeInconsistentValues(head, tail, constraint, variables) { + // Removes inconsistent values from the tail node. A value is + // inconsistent when if the `tail` is assigned that value, there are + // no values in `head`'s domain that satisfies the constraint. + var hv = variables[head], tv = variables[tail]; + var validTailValues = tv.filter(function (t) { + return hv.some(function (h) { + return constraint(h, t); + }); + }); + var removed = tv.length != validTailValues.length; + variables[tail] = validTailValues; + return removed; + } + + function incomingConstraints(node) { + // Returns all the constraints where `node` is the head node. + return csp.constraints.filter(function (c) { + return c[0] == node; + }); + } + + var queue = csp.constraints.slice(), + variables = partialAssignment(assigned, unassigned); + while (queue.length) { // While there are more constraints to test. + var c = queue.shift(), head = c[0], tail = c[1], constraint = c[2]; + if (removeInconsistentValues(head, tail, constraint, variables)) { + // If values from the tail have been removed, incoming constraints + // to the tail must be rechecked. + queue = queue.concat(incomingConstraints(tail)); + } + } + return variables; +} + +function selectUnassignedVariable(unassigned) { + // Picks the next variable to assign according to the Minimum + // Remaining Values heuristic. Pick the variable with the fewest + // values remaining in its domain. This helps identify domain + // failures earlier. + var minKey = null, minLen = Number.POSITIVE_INFINITY; + for (var key in unassigned) { + var len = unassigned[key].length; + if (len < minLen) { minKey = key, minLen = len; } + } + return minKey; +} + +function orderValues(nextKey, assigned, unassigned, csp) { + // Orders the values of an unassigned variable according to the + // Least Constraining Values heuristic. Perform arc consistency + // on each possible value, and order variables according to the + // how many values were eliminated from all the domains (fewest + // eliminated in the front). This helps makes success more likely + // by keeping future options open. + + function countValues(vars) { + var sum = 0; + for (var key in vars) { sum += vars[key].length; } + return sum; + } + + function valuesEliminated(val) { + assigned[nextKey] = [val]; + var newLength = countValues(enforceConsistency(assigned, unassigned, csp)); + delete assigned[nextKey]; + return newLength; + } + + // Cache valuesEliminated to be used in sort. + var cache = {}, values = unassigned[nextKey]; + values.forEach(function(val) { + cache[val] = valuesEliminated(val); + }); + // Descending order based on the number of domain values remaining. + values.sort(function (a, b) { return cache[b] - cache[a]; }); + return values; +} + +// Taken from d3 source. Makes `csp` usable in other scripts. +if (typeof define === 'function' && define.amd) { + define(CSP); +} else if (typeof module === 'object' && module.exports) { + module.exports = CSP; +} else { + this.csp = CSP; +} + +}(); -- cgit v1.2.3