回溯法求解数独问题的思路和代码
在刷题的时候遇到了一个求解数独的问题，用回溯法写了以下代码，记录一下，之后探究有没有更好的算法。
算法思路：
①读取待求解数组，其中待填位置为0。
②将所有待填位置的两个坐标（行列）和目前数字封装起来压入栈1中。
③开一个栈2用于存储目前确定的答案。
④当栈1不为空的时候，取栈顶元素，从元素当前值加一开始依次到9判断是否可以填入，若可以则将当前元素压入栈2，否则压回栈1并且取出栈2栈顶元素押回栈1；
⑤重复④，直到栈1为空。
java代码如下：
public class Main {
public static void main(String[] args) {
Stack<Index> stack = new Stack<>();
Stack<Index> stack2 = new Stack<>();
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int[][] num = new int[9][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
int t = in.nextInt();
if (t == 0) {
stack.push(new Index(0, i, j));
}
num[i][j] = t;
}
}
while (!stack.isEmpty()) {
Index top = stack.pop();
int i = top.num + 1;
for (; i <= 9; i++) {
num[top.row][top.col] = i;
if (isRight(top.row, top.col, num)) {
top.num = i;
break;
}
}
if (i == 10 && !stack2.isEmpty()) { //没答案
num[top.row][top.col] = 0;
top.num = 0;
stack.push(top);
stack.push(stack2.pop());
} else {
stack2.push(top);
}
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 8; j++) {
System.out.print(num[i][j] + " ");
}
System.out.print(num[i][8]);
System.out.println();
}
}
}
private static boolean isRight(int row, int col, int[][] a) {
for (int i = 0; i < 9; i++) {
if (i == col || a[row][i] == 0) {
continue;
}
if (a[row][i] == a[row][col]) {
return false;
}
}
for (int i = 0; i < 9; i++) {
if (i == row || a[i][col] == 0) {
continue;
}
if (a[i][col] == a[row][col]) {
return false;
}
}
return true;
}
}
class Index {
public int num;
public int row;
public int col;
public Index(int num, int row, int col) {
this.num = num;
this.row = row;
this.col = col;
}
}
运行示例：