- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我希望实现一种非常简单的算法,该算法使用蛮力回溯来解决数独网格问题。我面临的问题是,在我的实现中,我为一个名为 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/
我正在使用混合效应模型,并且由于我的方法的特殊性我需要解决下面模型的积分,然后制作图表获得的估计值。 换句话说,我需要求解下面的积分: 其中,di^2 是我模型中的 Var3,dh 是混合效应模型对应
我有一个方程组,我想用数值方法求解它。给定起始种子,我想得到一个接近的解决方案。让我解释。 我有一个常量向量,X,值: X <- (c(1,-2,3,4)) 和一个向量 W 的权重: W <- (c(
假设我有以下方程组: a * b = 5 sqrt(a * b^2) = 10 如何求解 R 中 a 和 b 的这些方程? 我想这个问题可以说是一个优化问题,具有以下功能......? fn <- f
我在 R 中有一个简单的通量模型。它归结为两个微分方程,对模型中的两个状态变量进行建模,我们将它们称为 A和 B .它们被计算为四个分量通量的简单差分方程 flux1-flux4 , 5 个参数 p1
R有什么办法吗?求解给定单变量函数的反函数?动机是我以后告诉R使用值向量作为反函数的输入,以便它可以吐出反函数值。 例如,我有函数 y(x) = x^2 ,逆是 y = sqrt(x) .有没有办法R
我在字符串中有以下方程 y = 18774x + 82795 求解x我会这样做:- x = (y-82795) / 18774 我知道y的值 但是方程一直在变化,并且始终采用字符串格式 是否可以简单地
如果我用 diophantine(2*x+3*y-5*z-77) 我收到了这个结果。 {(t_0, -9*t_0 - 5*t_1 + 154, -5*t_0 - 3*t_1 + 77)} 到目前为止还
我正在尝试求解仅限于正解的 ODE,即: dx/dt=f(x) x>=0。 在 MATLAB 中这很容易实现。 R 是否有任何变通方法或包来将解决方案空间限制为仅正值? 这对我来说非常重要,不幸的是没
下面的 ANTLR 文法中的 'expr' 规则显然是相互左递归的。作为一个 ANTLR 新手,我很难解决这个问题。我已经阅读了 ANTLR 引用书中的“解决非 LL(*) 冲突”,但我仍然没有看到解
我有一个关于在 R 中求解函数的可能性的非常基本的问题,但知道答案确实有助于更好地理解 R。 我有以下等式: 0=-100/(1+r)+(100-50)/(1+r)^2+(100-50)/(1+r)^
我正在编写使用递归回溯来解决 8 个皇后问题的代码(将 n 个国际象棋皇后放在 n × n 的棋盘上,这样皇后就不会互相攻击)。 我的任务是创建两个方法:编写一个公共(public)solveQuee
我不知道在以下情况下如何进行,因为最后一个方程没有所有 4 个变量。所以使用了等式下面的代码,但这是错误的......有谁知道如何进行? 方程: 3a + 4b - 5c + d = 10 2a +
假设我们有这个递归关系,它出现在 AVL 树的分析中: F1 = 1 F2 = 2 Fn = Fn - 1 + Fn - 2 + 1(其中 n ≥ 3) 你将如何解决这个递归以获得 F(n) 的封闭形
在Maple中,有谁知道是否存在一个函数来求解变量?例如,我正在尝试求解 r 的 solve4r=(M-x^y)*(r^(-1)) mod (p-1)。所以我知道 M、x、y 和 p 的值,但不知道
我也问过这个here在声音设计论坛上,但问题是沉重的计算机科学/数学,所以它实际上可能属于这个论坛: 因此,通过读取文件中的二进制文件,我能够成功地找到关于 WAV 文件的所有信息,除了 big si
我有以下问题: 设 a 和 b 为 boolean 变量。是否可以设置 a 和 b 的值以使以下表达式的计算结果为 false? b or (((not a) or (not a)) or (a or
我需要用 C 求解这个超越方程: x = 2.0 - 0.5sen(x) 我试过这个: double x, newx, delta; x = 2.0 - 0.5; newx = sin(x); del
我在 Windows 上使用 OpenCV 3.1。 一段代码: RNG rng; // random number generator cv::Mat rVec = (cv::Mat_(3, 1)
我正在尝试求解一个包含 3 个变量和数量可变的方程的方程组。 基本上,系统的长度在 5 到 12 个方程之间,无论有多少个方程,我都试图求解 3 个变量。 看起来像这样: (x-A)**2 + (y-
我正在尝试为有限差分法设计一种算法,但我有点困惑。所讨论的 ODE 是 y''-5y'+10y = 10x,其中 y(0)=0 且 y(1)=100。所以我需要一种方法来以某种方式获得将从关系中乘以“
我是一名优秀的程序员,十分优秀!