37. 解数独

// LeetCode指定调用方法 
public void solveSudoku(char[][] board) {

    backtracking(board, 0, 0);

}

// 可选填入字符
char[] chars = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};

// 回溯
private boolean backtracking(char[][] board, int x, int y) {

    // 当该行的所有列都遍历完时，判断该行是否是最后一行，如果是则说明board已填完，直接结束，如果不是最后一行，则接着遍历下一行
    if (y == 9) {
        if (x == 8) {
            return true;
        }
        x++;
        y = 0;
    }

    // 如果该位置已填入字符，则遍历下一个位置，否则遍历字符1-9，判断是否可以填入
    if (board[x][y] != '.') {
        return backtracking(board, x, y + 1);
    } else {
        // 遍历字符1-9
        for (int i = 0; i < 9; i++) {
            // 判断字符是否可以填入
            if (isPut(board, x, y, chars[i])) {
                // 将该字符填入
                board[x][y] = chars[i];
                // 继续填下一个位置
                if (backtracking(board, x, y + 1)) {
                    return true;
                }
                // 复原该位置字符
                board[x][y] = '.';
            }
        }
    }
    
    return false;
}

// 判断字符ch是否可以填入board[x][y]
private boolean isPut(char[][] board, int x, int y, char ch) {

    // 判断行和列是否已有该字符，有则不能填入，返回false
    for (int i = 0; i < 9; i++) {
        if (board[x][i] == ch || board[i][y] == ch) {
            return false;
        }
    }

    // 判断 3x3 宫内是否已有该字符，有则不能填入，返回false
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[(x / 3) * 3 + i][(y / 3) * 3 + j] == ch) {
                return false;
            }
        }
    }

    return true;
}