# Immutable.js Solvers

A bit ago I wrote about writing a generic brute force solver (wow, was that really two months ago?). It got … complicate. Mostly, because every time I wrote a step function, I had to be careful to undo the same. Wouldn’t it be nice if we could just write a step function and get backtracking for ‘free’?

Well, with immutability you can!

It’s something you see all of the time with functional languages, but it’s less common in languages like JavaScript. In a nutshell, the idea is that once you create a datastructure, that structure will never change. If you want to (for example), add an element to a list, you instead create a new list which is defined as the old list with one more element. Something like this:

// With a traditional list
> ls = [1, 2, 3]
> ls.push(4)
> console.log(ls)
[1, 2, 3, 4]

// With an immutable list
> ls = List([1, 2, 3])
> ls.push(4)
> console.log(ls.toJS())
[1, 2, 3]
> ls = ls.push(4)
> console.log(ls.toJS())
[1, 2, 3, 4]


Pretty cool! Note, the first time in the last example, ls didn’t change. In the second example, it looks like it changed… but that’s because we changed ls to point to the new list:

> ls = List([1, 2, 3])
> ls2 = ls.push(4)
> console.log(ls)
[1, 2, 3]
> console.log(ls2)
[1, 2, 3, 4]


That gives you one huge advantage: If you add something to a list then try to solve a problem with that, any references to the original list aren’t changed. So if that branch doesn’t work out, you can just discard it and you still have the original list. There are a few performance downsides to doing it this way, but it’s really quite nice. Let’s make it work.

import { Map, List, Set, Record, fromJS } from 'immutable'

export function makeSolver({
generateNextStates, // state -> [{state, step: String}, ...] // The string is a description of the step
isValid,            // state -> Boolean: Is the given state valid
isSolved,           // state -> Boolean: Is the given state a solution
}) {

// Takes a state and returns {state, steps, iterations}
// If returnFirst is set, return the first solution we find; if not, keep looking and return the shortest solution
return (state) => {
let startTime = Date.now()

// Each node stores a state, it's parent, and the step to get to it
let Node = Record({
state: null,
previousNode: null,
step: null,
})

// Visited is a map of state into the node graph
let visited = Map()

// Calculate the steps to get to a specific node
let stepsTo = (node) => {
let steps = []

while (node) {
steps.unshift(node.step)
node = node.previousNode
}

return steps
}

// List of states to visit, paired with the steps taken to get to them
// Starts with the initial state and no steps (since we just started here)
let toVisit = List().push(Node({
state: fromJS(state),
step: 'start'
}))

// Count how many nodes we processed for logging purposes
let iterations = 0

// As long as we have at least one more node to visit, keep going
while (toVisit.size > 0) {
iterations++
if (iterations % 1000 == 0) console.log(iteration: ${iterations}, queue size:${toVisit.size})

// Pop off the new value we're working on
let currentNode = toVisit.first()
let {state: currentState, previousNode, step} = currentNode
toVisit = toVisit.shift()

// If this state is invalid, discard it and move on
if (!isValid(currentState)) {
continue
}

// If we have a solution:
// - If we're returning the first solution, return it and steps to get to it
// - If not, record it
if (isSolved(currentState)) {
return {
state: currentState.toJS(),
steps: stepsTo(currentNode),
iterations,
duration: (Date.now() - startTime) / 1000
}
}

// Otherwise, check if we've reached a new known state
if (visited.has(currentState)) {
continue
} else {
visited = visited.set(currentState, currentNode)
}

// A valid state that isn't a solution, check all neighbors from this state
for (let {state: nextState, step} of generateNextStates(currentState)) {
let newNode = Node({
state: nextState,
previousNode: currentNode,
step: step
})

// Depth first search adds to the beginning (search these before all current nodes)
toVisit = toVisit.unshift(newNode)
}
}
}
}


And that’s actually it. It’s pretty close to last time. We do have to tweak our Sudoku solver to use immutable data structures a bit to use all of this information, but only a few tweaks (mostly in the yield of generateNextStates and using .get instead of [] for indexing):

import { Set } from 'immutable'
import { makeSolver } from './solvers/immutable.js'

let indexes = [0, 1, 2, 3, 4, 5, 6, 7, 8]

let getRow = (state, row) => indexes.map(i => state.get(row).get(i))
let getCol = (state, col) => indexes.map(i => state.get(i).get(col))
let getCel = (state, cel) => indexes.map(i => state.get(3 * Math.floor(cel / 3) + Math.floor(i / 3)).get(3 * (cel % 3) + (i % 3)))

let getCelIndex = (r, c) => Math.floor(r / 3) * 3 + Math.floor(c / 3)

let hasDup = (vs) => vs.some(v1 => v1 != 0 && vs.filter(v2 => v1 == v2).length != 1)

let generateNextStates = function*(state) {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (state.get(i).get(j) === 0) {
for (let v = 1; v <= 9; v++) {
yield {
state: state.set(i, state.get(i).set(j, v)),
step: (${i},${j}) => ${v} } } return } } } } let isValid = function(state) { for (let p = 0; p < 9; p++) { if (hasDup(getRow(state, p)) || hasDup(getCol(state, p)) || hasDup(getCel(state, p))) return false } return true } let isSolved = function(state) { for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { if (state.get(i).get(j) === 0) return false } } for (let p = 0; p < 9; p++) { if (hasDup(getRow(state, p)) || hasDup(getCol(state, p)) || hasDup(getCel(state, p))) return false } return true } let solveSudoku = makeSolver({ generateNextStates, isValid, isSolved, returnFirst: true, debug: false, searchMode: 'dfs', }) let sudokuToString = (state) => state.map(row => row.join('')).join('\n') + '\n' export { solveSudoku, sudokuToString }  Pretty cool. Let’s try it: > import('./sudoku.js').then(({ solveSudoku, sudokuToString }) => { ... let input = [ ... [0,4,0,0,0,0,1,7,9], ... [0,0,2,0,0,8,0,5,4], ... [0,0,6,0,0,5,0,0,8], ... [0,8,0,0,7,0,9,1,0], ... [0,5,0,0,9,0,0,3,0], ... [0,1,9,0,6,0,0,4,0], ... [3,0,0,4,0,0,7,0,0], ... [5,7,0,1,0,0,2,0,0], ... [9,2,8,0,0,0,0,6,0] ... ] ... ... let {state, steps, iterations, duration} = solveSudoku(input) ... ... console.log(solved in${iterations} iterations over ${duration} seconds) ... console.log(sudokuToString(state)) ... }) solved in 485 iterations over 0.02 seconds 845632179 732918654 196745328 683574912 457291836 219863547 361429785 574186293 928357461  Nice. Now that we have a solver, let’s see just how crazy we can get with more options. For example, different search modes: • Breadth first search (check all possibilities of 1 step, then 2, etc) • Depth first search (go all the way down one branch before backtracking along the next) • Score best searching (assign a score to each state, work on the highest ones first) To do this, we add a searchMode parameter and then add in a few different cases for how we queue up new cases to check. I think the best part is that it’s actually simple code. If we’re searching depth first, we add new nodes to the same side of the list we’re taking from. Breadth first search adds to the opposite end. The more complicated one is scoring based. But since we’re controlling the order of the list, we can do a binary insertion and still be efficient (log(n) on the number of current nodes). Nice! ... let newNode = Node({ state: nextState, previousNode: currentNode, step: step, distance: distance + 1, }) // Depth first search adds to the beginning (search these before all current nodes) if (searchMode === 'dfs' || searchMode === undefined) { toVisit = toVisit.unshift(newNode) } // Breadth first search adds to the end (so we'll search these after all current nodes) else if (searchMode == 'bfs') { toVisit = toVisit.push(newNode) } // Functional search, calculates and includes a score // toVisit will be sorted by these scores descending // Highest scores will end up at the beginning of the list, so will be processed first // If score returns a constant score, this is equivalent to DFS else if (typeof (searchMode) === 'function') { // Calculate the score for the next state newNode = newNode.set('score', searchMode(nextState)) if (debug) console.log(scored new node${newNode.score}: ${newNode.state}) // Edge case, no nodes if (toVisit.size === 0) { toVisit = toVisit.push(newNode) continue } // Use a binary search to insert the scored node into the visited nodes let lo = 0 let hi = toVisit.size - 1 while (hi - lo > 1) { let mid = ((lo + hi) / 2) | 0 // Integer division by forcing cast to Int for | operator if (newNode.score >= toVisit.get(mid).score) { hi = mid } else { lo = mid } } toVisit = toVisit.insert(lo, newNode) } ...  While we’re at it, let’s add an ability to bail out early as well at the end of the same loop: // If we've spent too long, bail out let currentDuration = (Date.now() - startTime) / 1000 if (maxTime !== undefined && currentDuration > maxTime) { error = 'maxTime reached' break }  Another way we can tweak this search would be to try different move generators. For the case of Sudoku, we’re doing the most brute force solution of all right now where were’ starting in the top left and moving across, but we don’t have to. Instead, let’s start with the ‘fewest degrees of freedom’: those squares in the Sudoku that only have one or two options before those that can still be any number: let generateNextStates = function*(state) { // Find the empty cell with the fewest degrees of freedom let bestI = 0 let bestJ = 0 let bestDoF = 100 let bestVS = null for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { if (state.get(i).get(j) === 0) { let row = Set(getRow(state, i)) let col = Set(getCol(state, j)) let cel = Set(getCel(state, getCelIndex(i, j))) let all = row.union(col).union(cel) let dof = 10 - all.size if (bestVS === null || dof < bestDoF) { bestI = i bestJ = j bestDoF = dof bestVS = Set([1, 2, 3, 4, 5, 6, 7, 8, 9]).subtract(all) } } } } for (let v of bestVS) { yield { state: state.set(bestI, state.get(bestI).set(bestJ, v)), step: (${bestI}, ${bestJ}) =>${v}
}
}
}


A little bit more complicated, but it’s also much faster. Here are some tests with all of the given search methods (constant score always returns 1, it defaults to DFS; count DOF is like using the better generator). Try this on three problems of increasing difficulty and what do you have?

Search NameGenerator NameTest NameIterationsDurationIter/SecError
Depth First SearchFill from top lefteasy4850.0224250
Depth First SearchFill from top lefthard895243.58824951
Depth First SearchFill from top lefthardest24020530.0048006maxTime reached
Breadth First SearchFill from top lefteasy47540.036132056
Breadth First SearchFill from top lefthard16995216.28810434
Breadth First SearchFill from top lefthardest6972930.0052324maxTime reached
Constant scoreFill from top lefteasy4850.02222045
Constant scoreFill from top lefthard895244.14521598
Constant scoreFill from top lefthardest22573230.0037524maxTime reached
Count non-zero squaresFill from top lefteasy4850.01240417
Count non-zero squaresFill from top lefthard895244.04722121
Count non-zero squaresFill from top lefthardest22875830.0047624maxTime reached
Count degrees of freedomFill from top lefteasy35290.25513839
Count degrees of freedomFill from top lefthard779758.2889408
Count degrees of freedomFill from top lefthardest4864930.0091621maxTime reached
Depth First SearchFill fewest degrees of freedom firsteasy490.0133769
Depth First SearchFill fewest degrees of freedom firsthard20730.4454658
Depth First SearchFill fewest degrees of freedom firsthardest88954.1922122
Breadth First SearchFill fewest degrees of freedom firsteasy490.0059800
Breadth First SearchFill fewest degrees of freedom firsthard22320.4484982
Breadth First SearchFill fewest degrees of freedom firsthardest1893618.7681009
Constant scoreFill fewest degrees of freedom firsteasy490.0059800
Constant scoreFill fewest degrees of freedom firsthard20730.3675649
Constant scoreFill fewest degrees of freedom firsthardest88953.8552307
Count non-zero squaresFill fewest degrees of freedom firsteasy490.0059800
Count non-zero squaresFill fewest degrees of freedom firsthard20730.3775499
Count non-zero squaresFill fewest degrees of freedom firsthardest88953.7072400
Count degrees of freedomFill fewest degrees of freedom firsteasy490.0222227
Count degrees of freedomFill fewest degrees of freedom firsthard20901.1111881
Count degrees of freedomFill fewest degrees of freedom firsthardest91837.2461267

That’s pretty cool. The better generator really makes a huge difference, changing the fill from the top left to fill fewest degrees of freedom gives actually makes the hardest problem solveable in a few seconds rather than more than 30 on my machine. Check iterations, this is because you only have to check some 10,000 states before you find an answer, rather than half a million or more.

That’s even the case although we are definitely spending more time. The iterations/second is much higher, but it’s worth the cost.

On top of that, there are a few other changes. For example, depth first search is better than breadth first for this case for the same reason (500 versus 5000 iterations on harder problems, solving with almost no backtracking and only 50 iterations on the easiest).

There are still a few more tweaks that I want to do. In particular, I want to update the code that we can find the best solution rather than just the first one. To do that, we can use my visisted structure with one big tweak: when we go to a node we’ve seen before, if we’ve found a better path to it, store that. If we find a solution, mark down that node. At the end, search all solution nodes, and return the best.

But that can wait a day or two.

Until then, current source: