recursive backtracker

solver.js

// solver
var R = require('ramda');

function configure(isLeaf, isGoal, getChildren) {
  return function recursiveSolve(node, sideEffects) {
    return (isLeaf(node)) ? isGoal(node) && sideEffects(node):
        R.any(function(child) {
            sideEffects(child); 
            return recursiveSolve(child); 
        }, getChildren(node));
  };    
} 

module.exports = configure;
                           

solver2.js

// solver
var R = require('ramda');
var iter = require('./solverIterator');

function solver2(isLeaf, isGoal, getChildren) {
  var iter = solverIterator();
  return function recursiveSolve(node, sideEffects) {
    var iter;
    if (isLeaf(node)) {
      return isGoal(node) && sideEffects(node);
    } 
    candidate = {done: false};
    while(!candidate.done) {
      candidate = iter.next();
      recursiveSolve(candidate);
    }
    return false;    
  };    
} 

module.exports = solver2;
                           

solverIterator.js

var Grid = require('./Grid');

function solverIterator() {
  var index = 0;
  var len = index.length;

  return {
    next: function(grid, cell) {
      if (index < len) {
        index++;
        return { value: grid.clone().update(cell, cell.domain[index]), done: false };
      }
      return { done: true };
    }
  };
}

module.exports = solverIterator;

sudokuExample.js

var solver = require('./solver');

// This is an example configuration for the solver function, using sudoku solving as an example.

// isLeaf returns true if there are no unbound cells, false otherwise
function isLeaf(grid) {
  // assert all cells in the grid are bound
}

// isGoal returns true if the grid satisfies all the sudoku constraints
function isGoal(grid) {
  // assert all rows are populated 1-9
  // assert all columns are populated 1-9
  // assert all boxes are populated 1-9 
}

// getChildren returns an array of grids with one of the unbound cells bound to
// a value available in its domain. Would be nice to do this lazily.
function getChildren(grid) {
  var children = [];
  // find an unbound cell and determine its domain
  // for each value in the unbound cell's domain, generate a new grid with the cell
  // bound to that value and push the new grid onto the `children` array
  return children;
}

// side effects
function print(grid) {
    // output the grid
    return true;
}

// configure the backtracker to solve sudoku puzzles...
sudokuSolver = solver(isLeaf, isGoal, getChildren);

// run it
sudokuSolver(grid, print);