数独

题目：牛客网

解题思路：

看注释

public class Solution {
  public void solveSudoku(char[][] board) {
        //深度搜索
        dfs(board, 0);
    }
 
    private boolean dfs(char[][] board, int step) {
        // TODO Auto-generated method stub
        int  x, y;
        if (step == 81) {
            return isValidSudoku(board);
        } else {
            // 根据step确定行列x,y
            x = step / 9;
            y = step % 9;
            if (board[x][y] != '.') {
                // 如果x,y处不是'.'那么直接进一步深度搜索
                if (dfs(board, step + 1))
                    // 当第81步，最后一处有数字，说明已经深度搜索完毕，直接return出来
                    return true;
            } else {
                // 需要填写数字，填写1-9判断是不是有效的数独输入
                for (int i = 1; i < 10; i++) {
                    board[x][y] = (char) ('0' + i);
                    if (isValidSudoku(board))
                        if (dfs(board, step + 1))
                            return true;
                    //如果不是有效的数独，那么就回复现场继续尝试，当填了9也不行之后就
                    //return false回上一步
                    board[x][y] = '.';
                }
            }
            return false;
        }
    }
 
    public boolean isValidSudoku(char[][] board) {
        // 行遍历和列遍历
        for (int i = 0; i < 9; i++) {
            int[] nums = new int[9];
            for (int j = 0; j < 9; j++) {
                if (board[i][j] >= '1' && board[i][j] <= '9') {
                    if (nums[(int) (board[i][j] - '1')] == 1) {
                        return false;
                    } else {
                        nums[(int) (board[i][j] - '1')] = 1;
                    }
                }
            }
            int[] nums2 = new int[9];
            for (int j = 0; j < 9; j++) {
                if (board[j][i] >= '1' && board[j][i] <= '9') {
                    if (nums2[(int) (board[j][i] - '1')] != 0) {
                        return false;
                    } else {
                        nums2[(int) (board[j][i] - '1')] = 1;
                    }
                }
            }
        }
        // 遍历小九宮格
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int[] nums = new int[9];
                // 九宫格遍历
                for (int k = 0; k < 3; k++) {
                    for (int k2 = 0; k2 < 3; k2++) {
                        if (board[i * 3 + k][j * 3 + k2] >= '1'
                                && board[i * 3 + k][j * 3 + k2] <= '9') {
                            if (nums[(int) (board[i * 3 + k][j * 3 + k2] - '1')] != 0) {
                                return false;
                            } else {
                                nums[(int) (board[i * 3 + k][j * 3 + k2] - '1')] = 1;
                            }
                        }
                    }
                }
            }
        }
        return true;
    }
}