具有反向跟踪的数独求解算法
我正在寻求实现一个非常简单的算法,该算法使用powershell反向跟踪来解决数独网格。 我面临的问题是,在我的实现中,我为一个名为row
和col
的Sudoku
类包含了两个实例变量,它们对应于表示Sudoku网格的二维数组中的空单元格的行和列。
当我的solve()
方法执行时,它首先检查是否没有任何空单元格,在这种情况下拼图已经完成。 否则,同一方法将空单元格的行和列分配给包含网格的Sudoku
对象的实例变量row
和col
。 之后,for循环通过方法调用isSafe(int n)
validation可以在该空单元格中放置哪个数字(此方法检查是否满足拼图的约束,我可以保证它完美地运行)。 因此, 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;
这是一种合理的方法吗?
实际上,您并不需要堆栈或递归。 您只需要一种有序的方式来访问单元格(请参阅下面的代码)。 这个解决方案不会像递归版本那样给你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 Sudoku Solver
该实现类似于八皇后拼图的标准回溯方法。
通过将它们存储在Sudoku类的Stack实例变量中,我能够存储每个递归调用时保持松散的空单元格的’row’和’col’值。 findNextZero()方法将’row’和’col’值压缩为两个空堆栈。 然后,我重新构建了程序的其余部分以通过peek()方法访问此信息,如果我不得不回溯,我只需弹出最后两个值并将与这些值对应的网格上的数字设置为0。