domain = [
-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
]
csp = ({
variables: {
x1: domain,
x2: domain,
x3: domain
},
constraints: [
{
dependencies: ["x1", "x2", "x3"],
condition: (x) => (3 * x.x1 + 2 * x.x2 - x.x3 === 1 ? 1 : 0)
},
{
dependencies: ["x1", "x2", "x3"],
condition: (x) => (2 * x.x1 - 2 * x.x2 + 4 * x.x3 === -2 ? 1 : 0)
},
{
dependencies: ["x1", "x2", "x3"],
condition: (x) => (-x.x1 + 0.5 * x.x2 - x.x3 === 0 ? 1 : 0)
}
]
})
function isAssignmentComplete(assignment, csp) {
for (let key of Object.keys(csp.variables)) {
if (assignment[key] === undefined) {
return false;
}
}
return true;
}
function evaluateAssignment(assignment, csp) {
return csp.constraints
.map((constraint) => {
return constraint.condition(assignment);
})
.reduce((t, v) => t + v);
}
function chooseNextVariable(assignment, csp) {
for (const key of Object.keys(csp.variables)) {
if (assignment[key] === undefined) {
return key;
}
}
return null;
}
function orderPossibleValues(csp, variable) {
return csp.variables[variable] ?? [];
}
function cspBacktrack(assignment, value, csp, solution) {
if (isAssignmentComplete(assignment, csp)) {
if (value > solution.bestValue ?? 0) {
solution.bestValue = value;
solution.bestAssignment = assignment;
}
return;
}
const nextVariable = chooseNextVariable(assignment, csp);
const possibleValues = orderPossibleValues(csp, nextVariable);
for (const possibleValue of possibleValues) {
const newAssignment = { ...assignment };
newAssignment[nextVariable] = possibleValue;
const newValue = evaluateAssignment(newAssignment, csp);
if (newValue <= 0) continue;
// TODO: Forward Lookahead
cspBacktrack(newAssignment, newValue, csp, solution);
}
}
solution = ({ bestValue: 0, bestAssignment: {} })
cspBacktrack({}, 0, csp, solution)
solution
function cspToDot(csp) {
let dotCode = `graph g {
rankdir = LR;\n`;
for (const variable in csp.variables) {
dotCode += `${variable} [shape="circle"]\n`;
}
for (const constraint in csp.constraints) {
dotCode += `${constraint} [shape="square"]\n`;
for (const dependency of csp.constraints[constraint].dependencies) {
dotCode += `${constraint} -- ${dependency}\n`;
}
}
dotCode += `}\n`;
return dotCode;
}
dot`${cspToDot(csp)}`
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.
