class Solution {
    private char[][] board;
    private int[] row;
    private int[] col;
    private int[] box;

    public void solveSudoku(char[][] board) {
        this.board = board;
        row = new int[9];
        col = new int[9];
        box = new int[9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c;
                if ((c = board[i][j]) == '.') continue;
                set(i, j, c - '0');
            }
        }
        dfs(0, 0);
    }

    private boolean dfs(int y, int x) {
        for (; y < 9; y++) {
            for (x = x == 9 ? 0 : x; x < 9; x++) {
                char c;
                if ((c = board[y][x]) != '.') continue;
                int i = 1;
                for (; i <= 9; i++) {
                    if (!set(y, x, i)) continue;
                    if (dfs(y, x)) return true;
                    unset(y, x);
                }
                if (i == 10) return false;
            }
        }
        return true;
    }

    private boolean set(int y, int x, int val) {
        int mask = 1 << val;
        int id = y / 3 * 3 + x / 3;
        if ((row[y] & mask) != 0 || (col[x] & mask) != 0 || (box[id] & mask) != 0) return false;
        row[y] |= mask;
        col[x] |= mask;
        box[id] |= mask;
        board[y][x] = (char)(val + '0');
        return true;
    }

    private void unset(int y, int x) {
        int val = board[y][x] - '0';
        int mask = (0x400 - 1) ^ (1 << val);
        int id = y / 3 * 3 + x / 3;
        row[y] &= mask;
        col[x] &= mask;
        box[id] &= mask;
        board[y][x] = '.';
    }
}