What's wrong with my js code? Help please.


  • 0
    T

    I try to use stack instead of recursion but failed. Could anyone help to check why it goes wrong?

    /**
     * @param {character[][]} board
     * @return {void} Do not return anything, modify board in-place instead.
     */
    var solveSudoku = function(board) {
        var r = new Array(9),
            c = new Array(9),
            b = new Array(9);
        var i, j;
        for (i = 0;i < 9;++i) {
            r[i] = new Array(9);
            c[i] = new Array(9);
            b[i] = new Array(9);
        }
    
        for (i = 0;i < 9;++i) {
            for (j = 0;j < 9;++j) {
                if (board[i][j] === '.') {
                    continue;
                }
                var temp = +board[i][j] - 1;
                r[i][temp] = c[temp][j] = b[~~(j/3)+~~(i/3)*3][temp] = true;
            }
        }
        i = j = 0;
        var stack = [],k, coord;
        while (true) {
            if (i === 9 && j === 0) {
                break;
            }
            if (board[i][j] === '.') {
                for (k = 0;k < 9;++k) {
                    if (!(r[i][k] || c[k][j] || b[~~(j/3)+~~(i/3)*3][k])) {
                        board[i][j] = String(k+1);
                        r[i][k] = c[k][j] = b[~~(j/3)+~~(i/3)*3][k] = true;
                        stack.push({i:i,j:j,v:k});
                        break;
                    }
                }
                if (k >= 9) {
                    //Assume that there exists at least one solution
                    while ((coord=stack.pop()).v >= 8) {
                        board[coord.i][coord.j] = '.';
                        r[coord.i][coord.v] 
                            = c[coord.v][coord.j] 
                            = b[~~(coord.j/3)+~~(coord.i/3)*3][coord.v] = false;
                    }
                    i = coord.i;
                    j = coord.j;
                    board[i][j] = String(coord.v +2);
                    stack.push({i:i,j:j,v:coord.v + 1});
                    r[i][coord.v] 
                        = c[coord.v][j] 
                        = b[~~(j/3)+~~(i/3)*3][coord.v] = false;
                    r[i][coord.v + 1] 
                        = c[coord.v + 1][j] 
                        = b[~~(j/3)+~~(i/3)*3][coord.v + 1] = true;
                }
            }
            if (j >= 8) {
                j = 0;
                ++i;
            } else {
                ++j;
            }
        }
    };
    

    It is similar to valid sudoku.
    I use stack to store number and coordinates.
    I don't know how to debug it because console in chrome shows board don't update.

    Thanks a lot.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.