题解 | #HJ044 Sudoku#

import java.util.*;

/**
 * HJ44 Sudoku
 */
public class HJ044 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (sc.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] = sc.nextInt();
                    if (sudoku[i][j] == 0) {
                        need.add(new Pos(i, j));
                    }
                }
            }
            // DFS填充数独
            dfs(sudoku, need, 0);
        }
        sc.close();
    }

    // 返回值作为填充结束的标志，可以修改为无返回值函数，则打印所有满足条件的数独
    private 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;
    }

    private 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;

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