题解 | Sudoku

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    
    static List<int[]> list;
    static int[][] arr;

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        arr = new int[9][9];
        list = new ArrayList<>(); // 缺失数字的格子，即:需要填充的格子

        for(int r = 0; r < 9; r++) {
            for(int c = 0; c < 9; c++) {
                arr[r][c] = in.nextInt();
                if (arr[r][c] == 0) {
                    list.add(new int[]{r,c});
                }
            }
        }

        hand(0);

        for(int r = 0; r < 9; r++) {
            for(int c = 0; c < 9; c++) {
                System.out.printf("%d ", arr[r][c]);
            }
            System.out.println();
        }
    }


    // 从 arr 的 list[index] 位置开始填充, 返回所有格子是否填充完成
    static boolean hand(int index) {
        if (index == list.size()) {
            return true;
        }

        // 枚举 1-9 每个数字来填充 arr[r][c]
        int r = list.get(index)[0];
        int c = list.get(index)[1];

        for(int num = 1; num <= 9; num++) {
            if (isValid(r, c, num)) {
                arr[r][c] = num;
                if (hand(index + 1)) {
                    return true;
                }
                arr[r][c] = 0;
            }
        }

        return false;
    }


    // arr[r][c] 是否可以填充 num
    static boolean isValid(int r, int c, int num) {
        // 检查行，若当前行 r 已存在 num，说明不能填充
        for(int col = 0; col < 9; col++) {
            if (arr[r][col] == num) {
                return false;
            }
        }

        // 检查列
        for(int row = 0; row < 9; row++) {
            if (arr[row][c] == num) {
                return false;
            }
        }

        // 检查arr[r][c] 所属的 3*3 网格
        int startRow = r / 3 * 3;
        int startCol = c / 3 * 3;
        for(int row = startRow; row < startRow + 3; row++) {
            for(int col = startCol; col < startCol + 3; col++) {
                if (arr[row][col] == num) {
                    return false;
                }
            }
        }

        return true;
    }

}