如何通过此回溯找到第一个解决方案
我正在尝试编写一个只返回第一个可能解决方案的数独求解器。 我设法用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; }
你只需要实现一些非常简单的方法。
更改
if(board1.boardIsOk()) // check if the board is legal return nextCell(line, column); // continue
成
if(board1.boardIsOk()) { // check if the board is legal boolean solved = nextCell(line, column); // continue if (solved) { return true; ] } ... return false;