mreinstein · April 14, 2025 13:22 · Feb 19, 2020 · Feb 19, 2020
diff --git a/discrete-problem-solver.js b/discrete-problem-solver.js
@@ -14,7 +14,7 @@ function addVariable (problem, name, domain) {
 
 
 function changeVariable (problem, name, newdomain) {
-	if (problem.variables[name])
+    if (problem.variables[name])
       problem.variables[name].domain = newdomain     
     else
       throw new Error('Attempted to change a nonexistant variable.')

diff --git a/discrete-problem-solver.js b/discrete-problem-solver.js
@@ -0,0 +1,113 @@
+
+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 }
diff --git a/usage.js b/usage.js
@@ -0,0 +1,26 @@
+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))