题解 | #Sudoku#

import java.util.*;

public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int[][] sudoku = new int[9][9];
                        // 记录需要填充的数组位置               
                        LinkedList<Pos> need = new LinkedList<>();
                        // 构造数组 + 标记
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sudoku[i][j] = in.nextInt();
                    if (sudoku[i][j] == 0) {
                        need.add(new Pos(i, j));
                    }
                }
            }
                        // DFS填充数独
            dfs(sudoku, need, 0);
        }
    }

        // 返回值作为填充结束的标志，可以修改为无返回值函数，则打印所有满足条件的数独
    public static boolean dfs(int[][] sudoku, LinkedList<Pos> need, int index) {
                // 填充完结标志
        if (need.size() == index) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(sudoku[i][j] + " ");
                }
                System.out.println("");
            }
            return true;
        }
                // 当前填充位置
        Pos p = need.get(index);
                // 获取当前位置可填充的数字列表
        List<Integer> list = fillNum(sudoku, p);
                // 循环尝试填充一个值作为新的数独表，并填充下一个位置的数字
        for (int num : list) {
            sudoku[p.x][p.y] = num;
            if (dfs(sudoku, need, index + 1)) {
                return true;
            }
        }
                // 回溯时需要把改变的值还原
        sudoku[p.x][p.y] = 0;
        return false;
    }

    public static List<Integer> fillNum(int[][] sudoku, Pos pos) {
        int[] num = new int[10];
                // 搜索横纵方向的值
        for (int i = 0; i < 9; i++){
            num[sudoku[pos.x][i]]++;
            num[sudoku[i][pos.y]]++;
        }

                // 搜索方块的值
        int startX = pos.x / 3 * 3;
        int startY = pos.y / 3 * 3;
        for (int i = startX; i < startX + 3; i++) {
            for (int j = startY; j < startY + 3; j++) {
                num[sudoku[i][j]]++;
            }
        }

                // 找出哪些值一个都没有出现的即为当前位置可以填充的值
        List<Integer> numList = new ArrayList<>();
        for (int i = 1; i < 10; i++) {
            if (num[i] == 0) {
                numList.add(i);
            }
        }
        return numList;
    }

        // 构造的位置类，方便操作
    public static class Pos {
        int x;
        int y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}