我希望实现一种非常简单的算法,该算法使用蛮力回溯来解决数独网格问题。我面临的问题是,在我的实现中,我为一个名为 row
和 col
的 Sudoku
类包含了两个实例变量,它们对应于表示数独网格的二维数组中空单元格的行和列。
当我的 solve()
方法执行时,它首先检查是否没有任何空单元格,在这种情况下拼图已经完成。否则,同一方法将空单元格的行和列分配给包含网格的 Sudoku
对象的实例变量 row
和 col
.之后,for 循环通过方法调用 isSafe(int n)
验证可以将哪个数字放入该空单元格(此方法检查是否满足拼图的约束,我可以保证它运行完美)。因此,isSafe()
方法在空单元格中放置一个数字,然后在 Sudoku
上再次递归调用 solve()
方法> 对象。
如果我们遇到无法满足的约束,那么我们将 0
重新分配给最后填充的 row
和 col
.这就是发现问题的地方!由于程序不断更新 row
和 col
变量,因此每次递归调用都会丢失旧实例。我一直在试图弄清楚如何存储这些值,以便程序在回溯时可以撤消操作。我考虑过将每个 col
和 row
推到一个堆栈,但我真的不确定该去哪里。
有人能告诉我解决这个问题的简单方法是什么吗?我没有包括整个类(class),如果您认为它有帮助,请告诉我,我会发布它。
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
和 col
整数压入堆栈。继续这样做,然后修改下面这行代码
this.Grid[this.row][this.col] = 0;
类似于
this.Grid[s.pop][s.pop] = 0;
这是一个合理的方法吗?
最佳答案
实际上,您并不真正需要堆栈或递归。您只需要一种有序的方式来访问单元格(请参见下面的代码)。此解决方案不会像递归版本那样为您提供 stackoverflow。
我会创建一个初始矩阵来标记预求解的单元格:
public boolean[][] findSolved(int[][] grid){
boolean[][] isSolved = new boolean[9][9];
for(int i=0; i<9; i++)
for(int j=0; j<9; j++)
isSolved[i][j] = grid[i][j] != 0;
return isSolved;
}
然后根据您是否回溯在单元格中前进或后退:
public boolean solve(int[][] grid){
boolean[][] isSolved = findSolved(grid);
int row, col, k = 0;
boolean backtracking = false;
while( k >= 0 && k < 81){
// Find row and col
row = k/9;
col = k%9;
// Only handle the unsolved cells
if(!isSolved[row][col]){
grid[row][col]++;
// Find next valid value to try, if one exists
while(!isSafe(grid, row, col) && grid[row][col] < 9)
grid[row][col]++;
if(grid[row][col] >= 9){
// no valid value exists. Reset cell and backtrack
grid[row][col] = 0;
backtracking = true;
} else{
// a valid value exists, move forward
backtracking = false;
}
}
// if backtracking move back one, otherwise move forward 1.
k += backtracking ? -1:1
}
// k will either equal 81 if done or -1 if there was no solution.
return k == 81;
}
关于java - 具有回溯法的数独求解算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19969978/