题解 | #Sudoku#

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[][] arrs = new int[9][9];
        //记录0的坐标
        List<Pos> fillList = new ArrayList<>();
        for (int i = 0 ; i < 9 ; i++) {
            for (int j = 0; j < 9; j++) {
                arrs[i][j] = in.nextInt();
                if (arrs[i][j] == 0) {
                    fillList.add(new Pos(i, j));
                }
            }
        }
        //开始计算0的真正值
        fillVal(arrs, fillList);

        //打印
        for (int i = 0 ; i < 9 ; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(arrs[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    public static boolean fillVal(int[][] arrs, List<Pos> fillList) {
        //开始计算0的真正值
        for (Pos pos : fillList) {
            int x = pos.getX();
            int y = pos.getY();
            if (arrs[x][y] != 0) {
                continue;
            }
            //尝试填值
            for (int i = 1; i <= 9 ; i++) {
                if (checkVal(arrs, x, y, i)) {
                    arrs[x][y] = i;
                    if (fillVal(arrs, fillList)) {
                        return true;
                    }
                    //递归回退
                    arrs[x][y] = 0;
                }
            }
            //1~9都不行,回退
            return false;
        }
        //所有值填写完毕
        return true;
    }

    public static boolean checkVal(int[][] arrs, int x, int y, int val) {
        return checkValInRow(arrs, x, val)
               && checkValInCol(arrs, y, val)
               && checkValInNine(arrs, x, y, val);
    }

    //在行中校验
    public static boolean checkValInRow(int[][] arrs, int x, int val) {
        for (int i = 0 ; i < 9 ; i++) {
            if (val == arrs[x][i]) {
                return false;
            }
        }
        return true;
    }

    //根据列计算可能值
    public static boolean checkValInCol(int[][] arrs, int y, int val) {
        for (int i = 0 ; i < 9 ; i++) {
            if (arrs[i][y] == val) {
                return false;
            }
        }
        return true;
    }

    //根据九宫格计算可能值
    public static boolean checkValInNine(int[][] arrs, int x, int y, int val) {
        int row = x / 3;
        int col = y / 3;
        for (int i = row * 3 ; i < (row + 1) * 3 ; i++) {
            for (int j = col * 3 ; j < (col + 1) * 3; j++) {
                if (arrs[i][j] == val) {
                    return false;
                }
            }
        }
        return true;
    }

    static class Pos {
        private int x;
        private int y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }
}