题解 | #Sudoku#

参考一位大佬的题解，还是基于dfs的思想来猜测0位置可以填的数有哪些，如果导致后序不行，则需要回溯。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[][] board = new int[9][9];
        for (int i =0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                board[i][j] = sc.nextInt();
            }
        }
        Sudoku(board);
        for(int i=0;i<9;i++){
            for(int j=0;j<8;j++){
                System.out.print(board[i][j] + " ");
            }
            System.out.println(board[i][8]);//换行，每一行的最后一个数字
        }
    }

    /**
     总体思路还是dfs思想，对于棋盘的某个位置，判断其放置1-9位置的数字是否合法
     若此位置添加k合法，则判断整个board是否合法，若已经合法则退出，若不和法则dfs调用
    */
    public static boolean Sudoku(int[][] board) {
        // 逐行遍历，若有零，则进入操作
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == 0) {
                    // 一次测试此位置填入1-9是否合适
                    for (int k = 1; k <= 9; k++) {
                        if (isValidSelect(k, i, j, board)) {
                            board[i][j] = k;
                            // dfs调用
                            if (Sudoku(board)) {
                                return true;
                            }
                            // 若上述的dfs调用后，数独还是未完成，则需要回溯
                            board[i][j] = 0;
                        }
                    }
                    // 进行到此步，说明没有找到解
                    return false;
                }
            }
        }
        // 说明上面的格子里没有0，则返回true
        return true;
    }

    /**
     * 判断位置[row][col]填入k，在行 列 小格上是否合法
     */
    public static boolean isValidSelect(int k, int row, int col, int[][] board) {
        // 行
        for (int i = 0; i < 9; i++){
            if (board[row][i] == k){
                return false;
            }
        }
        // 列
        for (int j = 0; j < 9; j++){
            if (board[j][col] == k){
                return false;
            }
        }
        // 格
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == k){
                    return false;
                }
            }
        }
        return true;
    }
}