题解 | #Sudoku#

import java.util.*;

public class Main{

    public static void main(String[] agrs) {

        Scanner scan = new Scanner(System.in);

        int[][] a = new int[9][9];
        for (int i = 0; i < 9; i ++) {
            for (int j = 0; j < 9; j ++) {
                a[i][j] = scan.nextInt();
            }
        }

        resolve(a);

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

    private static boolean resolve(int[][] a) {
        for (int i = 0; i < 9; i ++) {
            for (int j = 0; j < 9; j ++) {

                /**
                 * 对于空缺的位置从 1-9 依次填入，如果 1-9 符合数独规则
                 *         则基于此尝试递归解决数独，否则回溯
                 */
                if (a[i][j] == 0) {
                    for (int k = 1; k < 10; k ++) {
                        a[i][j] = k;

                        // 校验数独规则
                        if (check(i, j, k, a)) {

                            // 规则符合则递归解决数独
                            if (resolve(a)) {

                                // 数独解决
                                return true;
                            }
                        }

                        // 回溯
                        a[i][j] = 0;
                    }

                    // 9 个数字尝试完都不行则该数独无法解决
                    return false;
                }
            }
        }

        // 没有数字为 0，即数独已经解决
        return true;
    }

    private static boolean check(int i, int j, int v, int[][] a) {

        return checkI(i, j, a) && checkJ(i, j, a) && checkS(i, j, a);
    }

    private static boolean checkI(int i, int j, int[][] a) {
        for (int index = 0; index < 9; index ++) {
            if (index != j && a[i][index] == a[i][j]) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkJ(int i, int j, int[][] a) {
        for (int index = 0; index < 9; index ++) {
            if (index != i && a[index][j] == a[i][j]) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkS(int i, int j, int[][] a) {
        int imin = (i / 3) * 3;
        int jmin = (j / 3) * 3;
        for (int x = imin; x < imin + 3; x ++) {
            for (int y = jmin; y < jmin + 3; y ++) {
                if (x != i && j != i && a[x][y] == a[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}