My Java solution using iterative backtracking


  • 0
    Y
    public class Solution {
        public void solveSudoku(char[][] board) {
            Deque<Integer> deque = new ArrayDeque<>();
            char c = '1';
            for(int i=0;i<9;i++) {
                for(int j=0;j<9;j++) {
                    if(board[i][j] != '.') continue;
                    for(;c<='9';c++)
                        if(isValid(board, i, j, c)) {
                            board[i][j] = c;
                            deque.push((i<<4)+j);
                            c = '1';
                            break;
                        }
                    while(c > '9' && !deque.isEmpty()) {
                        int num = deque.pop();
                        i = num>>4;
                        j = num & 0xF;
                        c = ++board[i][j];
                        board[i][j--] = '.';
                    }
                }
            }
        }
        
        public boolean isValid(char[][] board, int i, int j, char c){
            for(int k = 0; k < 9; k++)
                if(board[k][j] == c || board[i][k] == c || board[i-i%3+k/3][j-j%3+k%3] == c)
                    return false;
            return true;
        }
    }

Log in to reply
 

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