题解 | #Sudoku#

贪心的选择可填数字最少的位置填充，每次填充之后重新调整各个待填充位置的可填数字，直到所有位置都被填充

import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[][] arr = new int[9][9];
        for (int i = 0; i < 9; i++) {
            String str = scanner.nextLine();
            String[] strArr = str.split(" ");
            for (int j = 0; j < 9; j++) {
                arr[i][j] = Integer.parseInt(strArr[j]);
            }
        }
        dfs(arr);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(arr[i][j]);
                if (j == 8) {
                    System.out.println();
                } else {
                    System.out.print(" ");
                }
            }
        }
    }

    public static void dfs(int[][] arr) {
        Map<String, Set<Integer>> map = updateMap(arr);
        int count = 1;
        while (true) {
            boolean isReturn = true;
            boolean idAdd = true;
            for (Map.Entry<String, Set<Integer>> entry : map.entrySet()) {
                Set<Integer> set = entry.getValue();
                if (set.size() != 0) {
                    isReturn = false;
                }
                if (set.size() == count) {
                    int temp = set.iterator().next();
                    int x = Integer.parseInt(entry.getKey().substring(0, 1));
                    int y = Integer.parseInt(entry.getKey().substring(1, 2));
                    arr[x][y] = temp;
                    set.remove(temp);
                    map = updateMap(arr);
                    count = 1;
                    idAdd = false;
                }
            }
            if (idAdd) {
                count ++;
            }
            if (isReturn) {
                return;
            }
        }
    }

    private static Set<Integer> getSet(int[][] arr, int i, int j) {
        Set<Integer> set = new HashSet<>(9);
        for (int x = 1; x < 10; x++) {
            set.add(x);
        }
        for (int x = 0; x < 9; x++) {
            if (arr[i][x] != 0) {
                set.remove(arr[i][x]);
            }
            if (arr[x][j] != 0) {
                set.remove(arr[x][j]);
            }
        }
        for (int x = (i / 3) * 3; x < (i / 3) * 3 + 3; x++) {
            for (int y = (j / 3) * 3; y < (j / 3) * 3 + 3; y++) {
                set.remove(arr[x][y]);
            }
        }
        return set;
    }

    private static Map<String, Set<Integer>> updateMap(int[][] arr) {
        Map<String, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (arr[i][j] == 0) {
                    Set<Integer> set = getSet(arr, i, j);
                    map.put(String.valueOf(i) + j, set);
                }
            }
        }
        return map;
    }

}