我正在尝试编写一个数独求解器,它将仅返回第一个可能的解决方案。
我设法用 void 方法打印所有可能的解决方案,但我不能在第一个发现时停止。
我知道首选方法是切换到布尔方法并返回true
上树——
但我找不到正确的写法。
我尝试的任何方式总是给出编译错误(method must return boolean
).
public boolean recursiveSolve(int line, int column) {
if(line == N) // N is the board size (9)
return true;
// if Cell is not empty - continue
if(board1.getCell(line, column) != 0) {
return nextCell(line, column);
}
// if Cell empty - solve
else {
for(int i = 1; i <= N; i++) {
board1.setCell(line, column, i); // set value to cell
if(board1.boardIsOk()) // check if the board is legal
return nextCell(line, column); // continue
}
board1.setCell(line, column, 0); // backtrack
}
}
private boolean nextCell(int line, int column) {
if(column < 8)
return recursiveSolve(line, column+1); // progress up the row
else
return recursiveSolve(line+1, 0); // progress down the lines
}
任何帮助将不胜感激。
这是大多数递归回溯问题的一些伪代码。
如果您已经找到解决方案,请报告成功。
for (当前位置的每一个可能的选择) {
做出这个选择并沿着这条路迈出一步。
使用递归从新的位置解决问题。
如果递归调用成功,向上级报告成功
等级。
退出当前选择恢复开始时的状态
循环的。
}
报告失败。
这是一些基于斯坦福大学讲座的实际代码。我用java重写了它并添加了注释。
Boolean SolveSudoku(int[][] grid)
{
int row, col;
if(!FindUnassignedLocation(grid, row, col))
//all locations successfully assigned
return true;
for(int num = 1; num <= 9; num++)
{
//if number is allowed to be placed in the square
if(NoConflicts(grid, row, col, num))
{
//place the number in the square
grid[row][col] = num;
//recur, if successful then stop
if(SolveSudoku(grid))
return true;
//undo and try again
grid[row][col] = UNASSIGNED;
}
}
//this triggers backtracking from early decisions
return false;
}
您只需要实现一些非常简单的方法。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)