/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    let empty = {};
    let rows = new Array(9).fill(void 0).map(()=>new Set());
    let cols = new Array(9).fill(void 0).map(()=>new Set());
    let blocks = new Array(9).fill(void 0).map(()=>new Set());

    for (let i=0;i<9;i++) {
        for (let j = 0; j < 9; j++) {
            let block = block_no(i, j);
            let v = board[i][j];
            if (v !== '.') {
                rows[i].add(v);
                cols[j].add(v);
                blocks[block].add(v);
                mark({block, i, j}, v);
            } else {
                mark({block, i, j}, v);
            }
        }
    }

    function block_no(i, j) {
        return (~~(i/3))*3 + ~~(j/3);
    }
    function mark({block, i, j}, v) {
        for (let n=0;n<9;n++){
            // not empty cell
            if ((i === n || j === n) && v !== '.') {
                if (empty[i+','+j]) {
                    delete empty[i+','+j];
                }
                continue;
            }

            // cols
            if (board[i][n] === '.') {
                let e = empty[i+','+n] = empty[i+','+n] || {block: block_no(i, n), i, j:n, maybe: new Set(['1','2','3','4','5','6','7','8','9'])};
                e.maybe.delete(v);
                if (!e.maybe.size) {
                    delete empty[i+','+n];
                }
            }
            
            // rows
            if (board[n][j] === '.') {
                let e = empty[n+','+j] = empty[n+','+j] || {block: block_no(n, j), i:n, j, maybe: new Set(['1','2','3','4','5','6','7','8','9'])};
                e.maybe.delete(v);
                if (!e.maybe.size) {
                    delete empty[n+','+j];
                }
            }
            
            // blocks
            let bi = ~~(block/3);
            let bj = block % 3;
            for (let bn=0;bn<9;bn++) {
                let i = bi*3 + ~~(bn/3);
                let j = bj*3 + bn % 3;
                if (board[i][j] === '.') {
                    let e = empty[i+','+j] = empty[i+','+j] || {block: block_no(i, j), i, j, maybe: new Set(['1','2','3','4','5','6','7','8','9'])};
                    e.maybe.delete(v);
                    if (!e.maybe.size) {
                        delete empty[i+','+j];
                    }
                }
            }
        }
    }

    function fill(i, j, block, v) {
        board[i][j] = v;
        empty[i+','+j].value = v;
        rows[i].add(v);
        cols[j].add(v);
        blocks[block].add(v);
    }

    function unfill(i, j, block, v) {
        board[i][j] = '.';
        empty[i+','+j].value = void 0;
        rows[i].delete(v);
        cols[j].delete(v);
        blocks[block].delete(v);
    }

    function deal() {
        let blanks = Object.keys(empty).map(k=>empty[k]).filter(m=>!m.value).sort((a,b)=>{
            return a.maybe.size - b.maybe.size;
        });

        for (let e of blanks) {
            let {block, i, j, value} = e;
            if (value) {continue;}
            let union = new Set([...rows[i], ...cols[j], ...blocks[block]]);
            let maybe = new Set(['1','2','3','4','5','6','7','8','9'].filter(v=>!union.has(v)));
            
            if (!maybe.size) {
                return false;
            }
            for (let v of [...maybe]) {
                // set for testing
                if (rows[i].has(v) || cols[j].has(v) || blocks[block].has(v)) {
                    return false;
                }
                fill(i, j, block, v);
                if (deal()) {
                    break; // found
                } else {
                    // rollback
                    unfill(i, j, block, v);
                    continue; // test next
                }
            }

            if (board[i][j] === '.') {
                return false;
            }
        }

        return true;
    }

    deal();
};

var sudoku = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]];
solveSudoku(sudoku);
console.info(sudoku);