数独求解算法
我期待实现一个非常简单的算法，它使用蛮力反向跟踪来解决数独网格。 我面临的问题是，在我的实现中，我包含了一个名为row和col的Sudoku类的两个实例变量，它们对应于表示Sudoku网格的二维数组中的空单元格的行和列。
当我的solve()方法执行时，首先检查是否没有空单元，在这种情况下，拼图已经完成。 否则，该方法将空单元格的行和列分配给包含网格的Sudoku对象的实例变量row和col 。 之后，for循环通过方法调用isSafe(int n)来验证哪个数字可以放在那个空单元格中（这个方法检查是否符合谜题约束，我可以保证它完美地运行）。 因此， isSafe()方法在空单元格中放置一个数字，然后再次对Sudoku对象上的solve()方法进行递归调用。
如果我们遇到了无法满足的约束条件，那么我们会重新分配一个0到最后row并填充col 。 这是发现问题的地方！ 由于程序不断更新row和col变量，因此每次递归调用都会丢失旧实例。 我一直在试图弄清楚如何存储这些值，以便程序在回溯时可以撤消操作。 我想过互推col和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和col整数推入堆栈之后。 继续这样做，然后修改下面的代码行
this.Grid[this.row][this.col] = 0;
到类似的东西
this.Grid[s.pop][s.pop] = 0;
这是一个合理的方法吗？
尝试此链接：Java数独解算器
该实现类似于八皇后拼图的标准回溯方法。
我能够通过将它们存储在Sudoku类的Stack实例变量中来存储每次递归调用时保留的空单元格的'row'和'col'值。 findNextZero（）方法将'row'和'col'值推入两个空的堆栈。 然后，我重新构造了程序的其余部分，通过peek（）方法访问这些信息，如果我不得不回溯，我只需弹出最后两个值，并将对应于这些值的网格上的数字设置为0。
实际上，你并不需要堆栈或递归。 你只需要一个有序的方式来访问单元格（见下面的代码）。 这个解决方案不会像递归版本那样给你提供堆栈。
我会创建一个初始矩阵来标记预先解析的单元格：
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;
}