Sudoku Solver

sudoku.coffee

# board = [
#     1,2,3,4,5,6,7,8,9
#     4,5,6,1,7,8,3,3,3
#     7,8,9,2,2,2,1,4,5
#     3,5,6,7,8,9,9,9,9
#     1,4,9,3,6,6,6,6,6
#     7,7,7,1,4,5,3,3,3
#     2,4,5,8,8,8,8,8,8
#     1,7,7,2,5,5,5,5,5
#     7,7,7,4,1,1,null,null,null
# ]


# board = [
#     1,2,3,4,5,6,7,8,9
#     4,5,6,7,8,9,1,2,3
#     7,8,9,1,2,3,4,5,6
#     2,3,1,5,6,4,8,9,7
#     null,null,null,null,null,null,null,null,null
#     8,9,7,2,3,1,5,6,4
#     3,1,2,6,4,5,9,7,8
#     6,4,5,9,7,8,3,1,2
#     9,7,8,3,1,2,6,4,5
# ]

board = [
    5,null,null,null,null,null,null,null,1
    null,null,null,null,null,null,null,null,null
    null,null,null,null,null,null,null,null,null
    null,null,null,null,null,null,null,null,null
    null,null,null,null,null,null,null,null,null
    null,null,null,null,null,null,null,null,null
    null,null,null,null,null,null,null,null,null
    null,null,null,null,null,null,null,null,null
    1,null,null,null,null,null,null,null,5
]



range = (x) ->
    result = []
    while x
        result.unshift(--x)
    return result


difference = (a, lists...) ->
    seen = {}
    lists.forEach (list) ->
        list.forEach (x) -> seen[x] = true
    a.filter (x) -> not seen[x]


compact = (list) ->
    list.filter (x) -> x isnt null


add = (n) -> (x) -> x + n


getCoordsFromIndex = (index) ->
    y = Math.ceil ((index+1) / 9)-1
    x = index - (y * 9)
    return {x, y}


uniques = (list) ->
    seen = {}
    result = []
    list.forEach (x) -> result.push(x) if (not seen[x]) and (seen[x] = true)
    return result


views = do ->

    row: (board, x, y) ->
        range(9).map (i) -> board[i + (y * 9)]

    column: (board, x, y) ->
        [x, y] = [x, y].map (a) -> Math.max(0, Math.min(8, a))
        range(9).map (i) -> board[x + (i * 9)]

    square: (board, x, y) ->
        [x, y] = [x, y].map (a) -> Math.max(0, Math.min(8, a))
        [offsetX, offsetY] = [x, y].map (a) -> (Math.ceil((a+1) / 3)-1) * 3
        result = []
        range(3).forEach (col) -> range(3).forEach (row) ->
            result.push board[((offsetY + col) * 9) + offsetX + row]
        return result


getPossibilities = (board, index) ->
    return null if board[index] isnt null
    {x, y} = getCoordsFromIndex(index)
    [row, column, square] = [views.row, views.column, views.square].map (fn) -> compact(fn board, x, y)
    perfectRow = range(9).map add(1)
    return difference(perfectRow, row, column, square)



verifyBoard = (board) ->
    board.forEach (value, index) ->
        seen = {}
        {x, y} = getCoordsFromIndex(index)
        origViews = [views.row, views.column, views.square].map (fn) -> compact(fn board, x, y)
        origViews
        .map (x) -> uniques(x)
        .forEach (a, index) ->
            if origViews[index].length isnt a.length then throw new Error \
            """
            Invalid board. Duplicate entries for (#{x}, #{y}) -> #{value}.
            """
    return true


isSolved = (board) ->
    verifyBoard(board)
    for cell in board
        return false if cell is null
    return true


render = (board) -> 
    buffer = []
    board.forEach (x, index) ->
        {x, y} = getCoordsFromIndex(index)
        buffer.push(board[index] or 0)
        if x is 8
            console.log buffer.join(',')
            buffer = []

solve = (board) ->
    board = board.slice(0)
    return board if isSolved(board)

    noChange = true
    possibilitySet = board.map (value, index) ->
        return null if value isnt null
        possibilities = getPossibilities(board, index)
        throw new Error("Cannot solve :(") if possibilities.length is 0
        noChange = false if possibilities.length is 1
        return possibilities

    if noChange
        for p, index in possibilitySet
            continue if p is null
            for value in p
                board[index] = value
                try return solve(board)
        throw new Error("Cannot solve :(")
    else
        return solve possibilitySet.map (p, index) ->
            return board[index] if p is null
            return p[0] if p.length is 1
            return null



board = solve(board)
render(board)