题解 | #数独#

class Solution {
    /**
     * 检查在数独(x,y)处填入num，是否合法
     * @param board 数独
     * @param x x
     * @param y y
     * @param num 要检测的数字
     * @return 是否合法
     */
    private boolean checkLegal(char[][] board, int x, int y, char num){
        // 检查同一列中是否存在相同数字
        for (char[] chars : board) {
            if (chars[x] == num) {
                return false;
            }
        }

        // 检查同一行中是否存在相同数字
        for (int i = 0; i < board[y].length; i++) {
            if(board[y][i] == num){
                return false;
            }
        }

        // 检查同一9宫格内是否存在相同数字
        int left = (x / 3) * 3;
        int top = (y / 3) * 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if(board[top+i][left+j] == num){
                    return false;
                }
            }
        }

        // 都没有，则合法
        return true;
    }

    /**
     * 从数独(x,y)处开始填入数字
     * @param board 数独
     * @param x x
     * @param y y
     * @return 是否有解
     */
    public boolean solve(char[][]board, int x, int y){
        // x超出范围，从下一行开头开始填
        if(x >= board[0].length){
            x = 0;
            y++;
        }
        // y超出范围，说明已填完
        if(y>=board.length){
            return true;
        }

        // 当前坐标需要填入数字
        if(board[y][x]=='.'){
            // 遍历1-9
            for (char k = '1'; k <= '9'; k++) {
                // 如果当前坐标可以填入k
                if(checkLegal(board, x, y, k)){
                    // 填入k
                    board[y][x] = k;
                    // 继续填下一个坐标的值，并判断之后的坐标是否有解
                    if(solve(board, x+1, y)){
                        // 如果之后的坐标有解，那么k值是对的，直接返回
                        return true;
                    }
                    // 否则说明填入k值无解，清空填入的k值
                    board[y][x] = '.';
                }
            }
            // 1-9都无解，返回无解
            return false;
        } else {
            // 当前坐标已有数字，则继续遍历下个坐标
            return solve(board, x+1, y);
        }
    }

    public void solveSudoku(char[][] board) {
        solve(board, 0, 0);
    }
}