问题描述：
数独：一种数字游戏，在9x9的格子里填写1~9这9个数，保证每一行、每一列、9个3x3的小九宫格里都包含了1~9这9个数。
给出一个空缺了部分数字的数独，求空缺的数字？
先定义一个类Elem，表示空位上填写的数字
class Elem {
int i, j; //坐标
int idx; //空位顺序标号，按从左到右、从上到下的顺序排列。
int val; //拟填的数字，取值为1~9
public Elem(int i, int j, int idx, int val) {
this.i = i;
this.j = j;
this.idx = idx;
this.val = val;
}
}
/** 在sudu的(m,n)可填写哪些数字 */
private static List<integer> vals(int[][] sudu, int m, int n) {/<integer>
List<integer> vals = new ArrayList<integer>();/<integer>/<integer>
for (int i = 1; i <= 9; i++) {
boolean exist = false; // 行、列、块中是否已存在与i相同的值
for (int j = 0; j < 9; j++) {
if ((j != n && sudu[m][j] == i) || (j != m && sudu[j][n] == i)) {
exist = true;
break;
}
int tm = 3 * (m / 3) + j / 3;
int tn = 3 * (n / 3) + j % 3;
if ((tm != m || tn != n) && sudu[tm][tn] == i) {
exist = true;
break;
}
}
if (exist) {
continue;
} else {
vals.add(i);
}
}
return vals;
}
//主程序
public static void test16() throws Exception {
/*
0 0 8 7 1 9 2 4 5
9 0 5 2 3 4 0 8 6
0 7 4 8 0 6 1 0 3
7 0 3 0 9 2 0 0 0
5 0 0 0 0 0 0 0 0
8 6 1 4 0 3 5 2 9
4 0 0 0 2 0 0 0 8
0 0 0 0 0 0 0 7 0
1 0 7 0 6 8 0 5 0
*/
Scanner scanner = new Scanner(System.in);
int[][] sudu = new int[9][];
int suduidx = 0;
while (scanner.hasNext()) {
String tstr = scanner.nextLine();
String[] tstrs = tstr.split("\\\\s+");
sudu[suduidx] = new int[9];
for (int i = 0; i < sudu.length; i++) {
sudu[suduidx][i] = Integer.parseInt(tstrs[i]);
}
suduidx++;
if (suduidx > 9) {
break;
}
}
scanner.close();
// 遍历二维数组，找到空位，从左到右、从上到下的顺序
List<integer> idxs = new ArrayList<integer>();/<integer>/<integer>
int count = 0;
for (int i = 0; i < sudu.length; i++) {
for (int j = 0; j < sudu.length; j++) {
if (sudu[i][j] == 0) {
idxs.add(i * sudu.length + j);
count++;
}
}
}
Stack<elem> stack = new Stack<elem>();/<elem>/<elem>
stack.push(new Elem(-1, -1, -1, Integer.MAX_VALUE)); // 根元素
while (!stack.isEmpty()) {
int m = 0, n = 0;
Elem e = stack.pop(); // 出栈赋值为sudu数组空位
if (count - 1 == e.idx) {// 如果是最后一个空位
m = e.i;
n = e.j;
sudu[m][n] = e.val;
System.out.println("---------- 开始输出 ----------");
for (int i = 0; i < sudu.length; i++) {
for (int j = 0; j < sudu.length - 1; j++) {
System.out.print(sudu[i][j] + " ");
}
System.out.println(sudu[i][8]);
}
System.out.println("---------- 结束输出 ----------");
} else { // 如果不是最后一个空位
if (-1 < e.idx) {
m = e.i;
n = e.j;
sudu[m][n] = e.val;
}
// 查找下一个空位可填写元素
int idx = idxs.get(e.idx + 1);
m = idx / sudu.length;
n = idx % sudu.length;
List<integer> vals = vals(sudu, m, n);/<integer>
if (vals.size() > 0) {
for (Integer in : vals) {
stack.push(new Elem(m, n, e.idx + 1, in));
}
} else {
if (!stack.isEmpty()) {
e = stack.peek();
for (int i = e.idx + 1; i < count; i++) {
int idx2 = idxs.get(i);
sudu[idx2 / sudu.length][idx2 % sudu.length] = 0;
}
}
}
}
}
}
如此可以打印出所有可填写的组合情况。
閱讀更多 道法自然理在悟心 的文章
