Last active
February 19, 2020 06:30
-
-
Save mreinstein/fe6c19caace8921666ab4d24bf7ed0a0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function createDiscreteProblem () { | |
| return { | |
| allAssignments: [ ], | |
| variables: { }, | |
| constraints: [ ] | |
| } | |
| } | |
| function addVariable (problem, name, domain) { | |
| problem.variables[name] = { name, domain } | |
| } | |
| function changeVariable (problem, name, newdomain) { | |
| if (problem.variables[name]) | |
| problem.variables[name].domain = newdomain | |
| else | |
| throw new Error('Attempted to change a nonexistant variable.') | |
| } | |
| function addConstraint (problem, variables, fn) { | |
| if (variables.length > 0) | |
| problem.constraints.push({ variables, fn }) | |
| } | |
| function getSolution (problem) { | |
| const assignments = { } | |
| return solve({ problem, assignments, single: true }) ? assignments : { } | |
| } | |
| function getSolutions (problem) { | |
| const assignments = { } | |
| solve({ problem, assignments, single: false }) | |
| return problem.allAssignments | |
| } | |
| function solve ({ problem, assignments, single }) { | |
| const { allAssignments, variables, constraints } = problem | |
| if (Object.keys(assignments).length === Object.keys(variables).length) { | |
| if (!single) | |
| allAssignments.push({ ...assignments }) | |
| return true | |
| } | |
| // find the next variable | |
| let nextVar = null | |
| for (const v in variables) { | |
| let found = false | |
| for (const a in assignments) { | |
| if (v === a) | |
| found = true | |
| } | |
| if (!found) { | |
| nextVar = variables[v] | |
| break | |
| } | |
| } | |
| function checkAssignment(nextVar, val) { | |
| assignments[nextVar.name] = val | |
| for (const c in constraints) { | |
| const args = [ ] | |
| let valid = true | |
| // try to build the argument list for this constraint... | |
| for (const k in constraints[c].variables) { | |
| const fp = constraints[c].variables[k] | |
| if (typeof assignments[fp] != "undefined") { | |
| args.push(assignments[fp]) | |
| } else { | |
| valid = false | |
| break | |
| } | |
| } | |
| if (valid) { | |
| // we can check it, so check it. | |
| if (!constraints[c].fn.apply(null, args)) { | |
| delete assignments[nextVar.name] | |
| return false | |
| } | |
| } | |
| } | |
| delete assignments[nextVar.name] | |
| return true | |
| } | |
| // try the values in its domain | |
| for (const j in nextVar.domain) { | |
| const val = nextVar.domain[j] | |
| //const valid = true | |
| if (checkAssignment(nextVar, val)) { | |
| assignments[nextVar.name] = val | |
| if (solve({ problem, assignments, single })) { | |
| if (single) | |
| return true | |
| } | |
| delete assignments[nextVar.name] | |
| } | |
| } | |
| return false | |
| } | |
| export default { createDiscreteProblem, addVariable, changeVariable, addConstraint, getSolution, getSolutions } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import solver from '../src/recursive-backtracking-solver.js' | |
| var p = solver.createDiscreteProblem() | |
| solver.addVariable(p, 'a', [ 1,2,3 ]) | |
| solver.addVariable(p, 'b', [ 4,5,6 ]) | |
| solver.addVariable(p, 'c', [ 6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 ]) | |
| solver.addConstraint( | |
| p, | |
| [ 'a', 'b' ], | |
| function (a, b) { return a*2 === b } | |
| ) | |
| solver.addConstraint( | |
| p, | |
| [ 'b', 'c' ], | |
| function (b, c) { return b*2 === c } | |
| ) | |
| // prints { a: 2, b: 4, c: 8 } | |
| console.log('one solution:', solver.getSolution(p)) | |
| // prints [ { a: 2, b: 4, c: 8 }, { a: 3, b: 6, c: 12 } ] | |
| console.log('all solutions:', solver.getSolutions(p)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment