题解 | #Sudoku#

/**
 * 数独
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        String a;
        int i = 0, j, k = 0;
        int[][] mat = new int[9][9];
        char[] complete = new char[162];//最后结果放入字符数组
        try {
            while ((a = r.readLine()) != null && !a.isEmpty()) splits(a, mat[i++]);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        numTry(mat);//进行模拟递归
        i = 0;
        while (i < 9) {
            j = 0;
            while (j < 9) {
                complete[k++] = (char) (mat[i][j] + '0');
                if (j != 8) complete[k++] = ' ';
                else complete[k++] = '\n';//最后一列数字后面加上换行符
                j++;
            }
            i++;
        }
        System.out.print(new String(complete));
    }

    //解析字符串
    private static void splits(String p, int[] arr) {
        char[] chs = p.toCharArray();
        int i = 0, j = 0, k = 0, l = chs.length, n = 0;
        while (i < l) {
            if (chs[i] == ' ') {
                if (j > 0) arr[k++] = n;
                n = 0;
                j = 0;
                i++;
                continue;
            }
            n *= 10;
            n += chs[i] - '0';
            if (i == l - 1) arr[k] = n;
            j++;
            i++;
        }
    }

    private static boolean numTry(int[][] mat) {
        int i, j = 0, k;
        boolean res = true;//初始设为true，表示假设能满足，后面再检验
        c0:
        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9; j++) {
                if (mat[i][j] != 0) continue;//数独的非0数跳过
                int[] num9 = new int[10];//数字数组初始元素为0
                getNum(mat, num9, i, j);//获得所有已用的1~9之间的数字
                k = 1;
                res = false;//有零元素，初始就设为false
                while (k < 10) {
                    if (num9[k] == 0) mat[i][j] = k;
                    else {//为1，表示该数字出现过，跳过
                        k++;
                        continue;
                    }
                    if (numTry(mat)) {
                        res = true;//能匹配设为true
                        break;
                    }
                    k++;
                }
                if (!res) {
                    mat[i][j] = 0;//回溯，重新置为0
                    break c0;//该位不能满足数独条件，跳出循环，方法返回false;
                }
            }
        }
        return res && i == 9 &&
               j == 9;//res为true，表示能够匹配，i和j能自增到0，表示9x9矩阵序列每一位都能满足
    }

    //获得该行该列的数字数组
    private static void getNum(int[][] m1, int[] num, int x, int y) {
        int b1 = x / 3 * 3;//所在3x3数组行的起始位置
        int b2 = y / 3 * 3;//所在3x3数组列的起始位置
        int i = 0, index;
        while (i < 9) {//所在行的所有非零数
            index = m1[x][i];
            num[index] = 1;
            i++;
        }
        i = 0;
        while (i < 9) {//所在列的所有非零数
            index = m1[i][y];
            num[index] = 1;
            i++;
        }
        i = b1;
        while (i < b1 + 3) {//所在3x3方格的所有非零数
            index = m1[i][b2];
            num[index] = 1;
            index = m1[i][b2 + 1];
            num[index] = 1;
            index = m1[i][b2 + 2];
            num[index] = 1;
            i++;
        }
    }
}