我正在寻求实现一种非常简单的算法,该算法使用强力回溯来解决数独网格。我面临的问题是,在我的实现中,我包含了两个实例变量Sudoku
类称为row
and col
,对应于表示数独网格的二维数组中空单元格的行和列。
When my solve()
方法执行时首先检查是否有任何空单元格,在这种情况下拼图已经完成。否则,相同的方法将空单元格的行和列分配给实例变量row
and col
of the Sudoku
包含网格的对象。然后,for 循环通过方法调用验证哪个数字可以放入该空单元格中isSafe(int n)
(此方法检查是否满足拼图的约束,我可以保证它完美运行)。所以isSafe()
方法将一个数字放入空单元格中,然后递归调用solve()
方法再次上Sudoku
object.
如果我们遇到无法满足的约束,那么我们重新分配0
到最后row
and col
那已经满了。到这里就发现问题了!由于程序不断更新row
and col
变量,然后每次递归调用都会丢失旧实例。我一直在试图弄清楚如何存储这些值,以便程序在回溯时可以撤消操作。我想过推动每个col
and row
到一个堆栈,但我真的不知道该去哪里。
有人可以告诉我解决这个问题的简单方法是什么吗?我不会包括整个班级,如果您认为这有帮助,请告诉我,我会发布它。
class Sudoku {
int SIZE, N, row, col;
int Grid[][];
public boolean solve() {
if (!this.findNextZero()) return true;
for (int num = 1; num <= 9; num++) {
if (isSafe(num)) {
this.Grid[this.row][this.col] = num;
if (this.solve()) return true;
this.Grid[this.row][this.col] = 0;
// this.Grid[oldRow][oldCol] = 0;
}
}
return false;
}
public boolean findNextZero() {
for (int i = 0; i < this.N; i++) {
for (int j = 0; j < this.N; j++) {
if (this.Grid[i][j] == 0) {
this.row = i;
this.col = j;
return true;
}
}
}
return false;
}
public boolean isSafe(int num) {
return !this.usedInRow(num)
&& !this.usedInColumn(num)
&& !this.usedInBox(num);
}
如果我要实现一个堆栈,以下内容是否有意义?之后findNextZero()
运营推动row
and col
整数入栈。继续这样做,然后修改以下代码行
this.Grid[this.row][this.col] = 0;
类似的东西
this.Grid[s.pop][s.pop] = 0;
这是一个合理的做法吗?