题解 | #Sudoku#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    //=======代码如下：========
    // 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;
    }
}