题解 | #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;
	}
}