题解 | #Sudoku#

DFS 时间复杂度较大，待优化

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.LinkedList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int[][] borad = new int[9][9];
    public static List<int[]> list = new ArrayList<>();
    public static Queue<int[]> queue = new LinkedList<>();
    public static List<int[][]> resultList = new ArrayList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    int value = in.nextInt();
                    if (value == 0) list.add(new int[]{i, j});
                    borad[i][j] = value;
                }
            }
        }
        Sudoku(0);
        int[][] rell = resultList.get(0);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (j == 8) {
                    System.out.println(rell[i][j]);
                } else {
                    System.out.print(rell[i][j] + " ");
                }
            }
        }
    }
    public static void Sudoku(int index) {
       if (index == list.size()) {
           int[][] result = new int[9][9];
           for (int i = 0; i < 9; i++) {
               for (int j = 0; j < 9; j++) {
                   result[i][j] = borad[i][j];
               }
           }
           resultList.add(result);
           return;
       }
        int[] post = list.get(index);
        int cow = post[0];
        int row = post[1];
       for (int i = 1; i < 10; i++) {
           if (isOk(post, i)) {
               borad[cow][row] = i;
               Sudoku(index + 1);
           }
           borad[cow][row] = 0;
       }
    }
    public static boolean isOk(int[] post, int q) {
        int cow = post[0];
        int row = post[1];
            //遍历行
            for (int j = 0; j < 9; j++) {
                if (borad[cow][j] == q) return false;
            }
            // 遍历列
            for (int j = 0; j < 9; j++) {
                 if (borad[j][row] == q) return false;
            }
            // 遍历3 X 3 表格
            for (int j = (cow / 3) * 3; j < (cow / 3) * 3 + 3; j++) {
                for (int k = (row / 3) * 3; k <  (row / 3) * 3 + 3; k++) {
                    if (borad[j][k] == q) return false;
                }
            }
        return true;
    }
}