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.

Start with immutable.js.

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: