/**
 * @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);
        }
    }

    function block_no(i, j) {
        return (~~(i / 3)) * 3 + ~~(j / 3);
    }
    function mark({ block, i, j }, v) {
        for (let n = 0; n < 9; n++) {
            // skip self if is 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.has(v)&&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.has(v)&&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.has(v)&&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() {
        // find empty cell order by maybe size
        let blanks = Object.keys(empty).map(k => empty[k]).filter(e => !e.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; } // maybe signed
            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)));

            // empty cell must has some maybe number
            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"]];
var sudoku = [[".","6",".","5","9","3",".",".","."],["9",".","1",".",".",".","5",".","."],[".","3",".","4",".",".",".","9","."],["1",".","8",".","2",".",".",".","4"],["4",".",".","3",".","9",".",".","1"],["2",".",".",".","1",".","6",".","9"],[".","8",".",".",".","6",".","2","."],[".",".","4",".",".",".","8",".","7"],[".",".",".","7","8","5",".","1","."]];
console.time();
solveSudoku(sudoku);
console.info(sudoku);
console.timeEnd();