sudoku solver.txt

class Solution {
    int n = 3, N = n * n;
    int[] status;
    char[][] board;
    boolean solved = false;
    public void solveSudoku(char[][] board) {
        // status: [rows : cols : boxes]
         status = new int[N * n];
        this.board = board;
        // fill the numbers
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] != '.')
                    placeNumber(board[i][j] - '0', i, j);            
            }
        }
        backtrack(0, 0);        
    }
    
    public void backtrack(int i, int j) {
        if (board[i][j] == '.') {
            for (int d = 1; d < 10; d++) {
                if (canPlace(d, i, j)) {
                    placeNumber(d, i, j);
                    afterPlace(i, j);
                    if (!solved) removeNumber(d, i, j);
                }
            }
        } else
            afterPlace(i, j);
    }
    
    public void placeNumber(int num, int i, int j) {
        status[i] |= (1 << num);
        status[N + j] |= (1 << num);
        int box = 3 * (i / 3) + (j / 3) + 2 * N; 
        status[box] |= (1 << num);
        board[i][j] = (char) (num + '0');
    }
    
    public void removeNumber(int num, int i, int j) {
        status[i] ^= (1 << num);
        status[N + j] ^= (1 << num);
        int box = 3 * (i / 3) + (j / 3) + 2 * N; 
        status[box] ^= (1 << num);
        board[i][j] = '.';
    }
    
    public void afterPlace(int i, int j) {
        if (i == N - 1 && j == N - 1) solved = true;
        else if (j == N - 1) backtrack(i + 1, 0); // move forward
        else backtrack(i, j + 1);
    }
    
    public boolean canPlace(int num, int i, int j) {
        if ((status[i] & (1 << num)) != 0) return false;
        if ((status[N + j] & (1 << num)) != 0) return false;
        int box = 3 * (i / 3) + (j / 3) + 2 * N; 
        if ((status[box] & (1 << num)) != 0) return false;
        return true;
    }
}