题目：
数独问题：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方法对数组的操控技巧，尤其是检查小九宫格这个部分。 |
转播
