// 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]

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

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

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 }

> 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

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

// If we've spent too long, bail out
let currentDuration = (Date.now() - startTime) / 1000
if (maxTime !== undefined && currentDuration > maxTime) {
    error = 'maxTime reached'
    break
}

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}`
        }
    }
}