题解 | #Sudoku#回溯+剪枝

import java.math.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.stream.*;
import java.util.regex.*;
import java.util.function.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String[][] m = new String[9][9];
        for (int i = 0; i < 9; i++) {
            m[i] = in.nextLine().split(" ");
        }
        fulfill(m);
        Arrays.stream(m).forEach(a-> {
            System.out.println(String.join(" ", a));
        });
    }

    // 回溯
    static boolean fulfill(String[][] m) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                String curr = m[i][j];
                if ("0".equals(curr)) {
                    // 剪枝
                    List<String> candidates = getCandidates(i, j, m);
                    if (candidates.isEmpty()) {
                        return false;
                    }
                    // 递归 DFS
                    for (String c : candidates) {
                        // continue fulfill 多次尝试
                        m[i][j] = c;
                        if (fulfill(m)) {
                            return true;
                        }
                        // 回溯（仅有 37 行是不可以的）
                        m[i][j] = "0";
                    }
                    return false;
                }
            }
        }
        return true;
    }

    static List<String> getCandidates(int i, int j, String[][] m) {
        String h = String.join("", m[i]);
        List<String> hSet = IntStream.rangeClosed(1, 9)
                            .mapToObj(String::valueOf)
                            // n->!h.contains(n) 可以换成 Predicate.not(h::contains)
                            .filter(n->!h.contains(n))
                            .collect(Collectors.toList());


        String[] vArr = new String[9];
        for (int k = 0; k < 9; k++) {
            vArr[k] = m[k][j];
        }
        String v = String.join("", vArr);
        List<String> vSet = IntStream.rangeClosed(1, 9)
                            .mapToObj(String::valueOf)
                            .filter(n->!v.contains(n))
                            .collect(Collectors.toList());

        String[] bArr = new String[9];
        int bIndex = 0;
        for (int p = 0; p < 3; p++) {
            for (int q = 0; q < 3; q++) {
                bArr[bIndex++] = m[(i / 3) * 3 + p][(j / 3) * 3 + q];
            }
        }
        String b = String.join("", bArr);
        List<String> bSet = IntStream.rangeClosed(1, 9)
                            .mapToObj(String::valueOf)
                            .filter(n->!b.contains(n))
                            .collect(Collectors.toList());

        vSet.retainAll(bSet);
        hSet.retainAll(vSet);
        return hSet;
    }
}