discrete-problem-solver.js

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 }

usage.js

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))