独数问题

题目：

数独问题：9*9的矩阵，要求每一行，每一列，每个九宫格都是1-9这九个数字且不能重复。

给定一9*9矩阵，里面有部分数空缺，要求找出满足上述要求的一个矩阵。

形如下方：

代码:

import java.util.Scanner;
public class 独数问题 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[][] table = {
                {'0','0','0','0','0','2','0','5','0'},
                {'0','7','8','0','0','0','3','0','0'},
                {'0','0','0','0','0','4','0','0','0'},
                {'5','0','0','0','0','0','0','0','0'},
                {'0','0','0','0','0','0','1','0','0'},
                {'0','0','0','0','3','0','7','0','8'},
                {'2','0','0','0','0','0','0','4','0'},
                {'0','0','0','0','0','5','0','9','0'},
                {'0','1','0','0','7','0','0','0','0'},
        };
        dfs(table,0,0);
    }
    
    private static void dfs(char[][] table,int  x,int y) {
        if(x==9) {
            print(table);
            System.exit(0);
        }
        if(table[x][y] == '0') {//虚位以待
            for(int k=1;k<10;k++) {
                if(check(table,x,y,k)) {
                    table[x][y] = (char)('0'+k);
                    dfs(table,x+(y+1)/9,(y+1)%9);
                }
            }
            table[x][y] = '0';//回溯
        }else {
            dfs(table,x+(y+1)/9,(y+1)%9);
        }
    }
    //打印
    private static void print(char[][] table) {
        for(int i=0;i<9;i++) {
            System.out.println(String.valueOf(table[i]));
        }
    }
    
    /**
     * 检查x,y坐标是否可以填k值
     * @param table
     * @param x
     * @param y
     * @param k
     * @return
     */
    private static boolean check(char[][] table,  int x, int y, int k) {
        //检查同行和同列
        for(int i=0;i<9;i++) {
            if(table[x][i] ==   (char)('0'+k))return false;
            if(table[i][y] ==  (char)('0'+k))return false;
        }
        //检查小九宫格
        for(int i=(x/3)*3;i<(x/3+1)*3;i++) {
            for(int j =(y/3)*3;j<(y/3+1)*3;j++)  {
                if(table[i][j] == (char)('0'+k))  return false;
            }
        }
        return true;
    }
}

这是一到很经典的深搜题，除了它经典的递归回溯的过程值得借鉴外，还有它的check方法对数组的操控技巧，尤其是检查小九宫格这个部分。