题解 | #Sudoku#

import java.util.*;

public class Main {
    /*
    一开始没什么思路，参考了题解：https://blog.nowcoder.net/n/9e0bf935707e492387116ee8c3e1c933
    （其实我的解法和这个题解差别挺大的，但确实有受到启发）
    
    思路：回溯法
    （思路有点像“N皇后”问题）
    总体思路：递归遍历每个空格，for循环尝试填入1-9
    
    全局变量：
        - int[][] map = new int[9][9]: 9x9的棋盘
        - boolean hasFinish：是否已正确填充所有空格
        - List<List<Integer>> spaces: 二维列表，存放所有空格的坐标
    步骤：
    1. 初始化棋盘，并记录所有空格的坐标（i,j）,存至二维列表spaces中
    
    2. 回溯函数（参数：下标index，即当前要填充的空格在spaces的下标）{
        终止条件：已遍历完所有空格（即index == spaces.size()），
                    并将hasFinish设为true
        for (遍历val：1-9，作为填入空格的值) {
            if (当前空格可以填入val) {
                填充空格;
                递归调用回溯函数（下一个空格下标：index+1）;
                if (hasFinish) {
                    return;
                }
                将空格值还原为0; // 回溯，撤销修改
            }
        }
    }
    */
    
    //=======代码如下：========
    // 9*9的棋盘
    static int[][] map = new int[9][9];
    // 二维列表，存放所有空格的坐标，如：[[0,0], [8,0]]
    static List<List<Integer>> spaces = new ArrayList<>();
    // 标记变量：是否已正确填充所有空格
    static boolean hasFinish = false;
    
    public static void main(String[] args) {
        // 初始化棋盘
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                map[i][j] = in.nextInt();
                // 将空格的坐标记录到spaces中
                if (map[i][j] == 0) {
                    spaces.add(Arrays.asList(i,j));
                }
            }
        }
        // 调用回溯函数
        backtrack(0);
        // 输出填充完毕后的棋盘
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
    
    /*
     * 回溯函数
     *     参数：index 当前要填充的空格在spaces的下标
     */
    static void backtrack(int index) {
        if (index == spaces.size()) {
            hasFinish = true;
            return;
        }
        // 获取空格的坐标
        List<Integer> space = spaces.get(index);
        int row = space.get(0);
        int col = space.get(1);
        // 遍历填入空格的可能值：1-9
        for (int val = 1; val <= 9; val++) {
            if (passCheck(row, col, val)) {
                map[row][col] = val;
                backtrack(index + 1);
                if (hasFinish) {
                    return;
                }
                map[row][col] = 0;
            }
        }
    }
    
    // 检测在map[row][col] 填入 val，是否满足数独条件
    static boolean passCheck(int row, int col, int val) {
        // 检测所在行
        for (int i = 0; i < 9; i++) {
            if (map[row][i] == val)
                return false;
        }
        
        // 检测所在列
        for (int i = 0; i < 9; i++) {
            if (map[i][col] == val)
                return false;
        }
        
        // 检测所在3*3小宫格
        int rowStart = row / 3 * 3; // 小宫格的行的最小值
        int colStart = col / 3 * 3; // 小宫格的列的最小值
        for (int i = rowStart; i < rowStart + 3; i++) {
            for (int j = colStart; j < colStart + 3; j++) {
                if (map[i][j] == val)
                    return false;
            }
        }
        // 通过所有检测
        return true;
    }
}