题解 | #Sudoku#学了个深度优先

import java.util.*;


public class Main {
  public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[][] grip = new int[9][9]; // 数独

        // 数据读取
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                grip[i][j] = in.nextInt();
            }
        }

        dfs(grip);

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 8; j++) {
                System.out.print(grip[i][j] + " ");
            }
            System.out.println(grip[i][8]);
        }
    }

    private static boolean dfs(int[][] grip) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (grip[i][j] != 0) {
                    continue;
                }
                for (int k = 1; k <= 9; k++) {
                    grip[i][j] = k;
                    if (!isLegal(grip, i, j)) {
                        grip[i][j] = 0;
                        continue;
                    }
                    if (dfs(grip)) {
                        return true;
                    }
                    grip[i][j] = 0;
                }
                return false;
            }
        }

        return true;
    }

    private static boolean isLegal(int[][] grip, int m, int n) {
        LinkedHashSet<Integer> pSet = new LinkedHashSet<>();
        LinkedHashSet<Integer> qSet = new LinkedHashSet<>();

        for (int i = 0; i < 9; i++) {
            int p = grip[m][i]; // 遍历一行
            int q = grip[i][n]; // 遍历一列
            if (p != 0) { // 该位置有数字
                if (pSet.contains(p)) return false; // 重复了
                else pSet.add(p);
            }
            if (q != 0) { // 该位置有数字
                if (qSet.contains(q)) return false; // 重复了
                else qSet.add(q);
            }
        }

        // 遍历小宫格
        LinkedHashSet<Integer> zSet = new LinkedHashSet<>();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int z = grip[m / 3 * 3 + i][n / 3 * 3+ j];
                if (z != 0) { // 该位置有数字
                    if (zSet.contains(z)) return false;
                    else zSet.add(z);
                }
            }
        }
        return true;
    }
}