Public
Edited
Oct 7, 2024
1 fork
Importers
12 stars
cspSolver = (constraints) => {
// Enforces variables consistency by removing inconsistent values
// from every constraint's tail node. This modifies the given variables
const constrain = (variables, key, value) => {
const cloneVar = ([id, domain]) => [id, domain.slice()];
const localVars = new Map(_(variables).map(cloneVar));
localVars.set(key, [value]);
const queue = constraints.slice();
while (queue.length) {
const [head, tail, constraint] = queue.shift();
const [hv, tv] = [localVars.get(head), localVars.get(tail)];
const validValues = tv.filter((t) => hv.some((h) => constraint(h, t)));
if (validValues.length < tv.length) {
localVars.set(tail, validValues);
// If values from the tail have been removed,
// incoming constraints to the tail must be rechecked.
for (const constraint of constraints)
if (constraint.from == tail) queue.push(constraint);
}
}
return localVars;
};
return function* (variables, options = {}) {
const log = options.logger || (() => {});
const recSolve = function* (variables) {
yield variables;
// Choose next variable to be resolved (Minimum Remaining Values heuristic):
// Picking the variable with the fewest values remaining in its domain
// helps identify domain failures earlier.
log(variables);
let [bestKey, min] = [null, Number.POSITIVE_INFINITY];
for (const [key, { length }] of variables) {
if (length < min && length > 1) (bestKey = key), (min = length);
if (!options.nobestkey && bestKey) break;
}
log(bestKey);
// If no variable needs to be resolved, problem is solved
if (bestKey == null) return;
const domain = variables.get(bestKey);
// Reorder values for this key (Least Constraining Values heuristic):
// Perform arc consistency on each possible value,
// and order values according to 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.
if (!options.noreorder) {
const sum = (sum, { length }) => sum + length;
const val2vars = (val) => constrain(variables, bestKey, val);
const val2sum = (val) => _(val2vars(val).values()).reduce(sum, 0);
const lut = new Map(domain.map((val) => [val, val2sum(val)]));
domain.sort((a, b) => lut.get(b) - lut.get(a));
}
// for each of these values:
for (const value of domain) {
// create local state of variables,
// assign value to variable previously chosen,
// and propagate constraints
const localVars = constrain(variables, bestKey, value);
// if one domain is empty, discard value
if (_(localVars).find(([, { length }]) => !length)) continue;
// recursively solve narrowed problem
let final;
for (const value of recSolve(localVars)) yield (final = value);
// if recursive solving found a solution, return
if (final) return;
}
// No solution has been found, return failure
yield;
};
yield* recSolve(variables);
};
}
sudokuProblem = (grid) => {
const _grid = _(grid); // iterable with optimized array functions
// Create one variable for each cell
const range = [..."123456789"]; // domains can be shared between variables
const domain = (char) => (isNaN(char) ? range : [char]);
const variables = new Map(_grid.map((char, i) => [i, domain(char)]));
// Keep indexes of initial values
const reducer = (arr, char, i) => (isNaN(char) ? arr : [...arr, i]);
const initial = _grid.reduce(reducer, []);
// Compute constrained sets of coords
const hLines = array(9, (y) => array(9, (x) => [x, y]));
const vLines = array(9, (x) => array(9, (y) => [x, y]));
const squares = array(9, (n) => i2xy(n, 3)).map(([I, J]) =>
array(3, (i) => array(3, (j) => [I * 3 + i, J * 3 + j])).flat()
);
// Express constraints for each set of coords
const constraints = [...hLines, ...vLines, ...squares] // gather all constrained sets
.map((coords) => coords.map(([x, y]) => x + 9 * y)) // coords -> indexes
.flatMap((indexes) => [...pairs(new Set(indexes))]) // enumerate possible pairs
.map(([i, j]) => [i, j, (v1, v2) => v1 != v2]); // create constraint for each pair
return { variables, initial, constraints };
}
sudoku2svg = (vars, initial) => {
const { svg, rect, text, group } = SVG;
const attrs = { fill: "none", stroke: "#DDD" };
const color = (index) => (initial.includes(index) ? "#F22" : "#000");
const label = (char, i) => text(char, { x: 6, y: 16, fill: color(i) });
const cells = Array.from(vars)
.map(([i, chars]) => [i, chars.length == 1 ? chars[0] : "", i2xy(i, 9)])
.map(([i, char, [x, y]]) => [label(char, i), [x * 20, y * 20]])
.map(([text, pos]) => group(pos, [rect([20, 20], attrs), text]));
const frames = array(9)
.map((_, i) => i2xy(i, 3))
.map(([x, y]) => rect([60, 60], { x: x * 60, y: y * 60 }));
const frameGroup = group([1, 1], frames, { fill: "none", stroke: "#000" });
return svg([182, 182], [group([1, 1], cells), frameGroup]);
}
{
if (!startSudoku) return;
const start = sudoku.generate("inhuman");
const { variables, initial, constraints } = sudokuProblem(start);
const solve = cspSolver(constraints);
for (const result of solve(variables))
if (result) yield sudoku2svg(result, initial);
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
