如何通过此回溯找到第一个解决方案

Question

我正在尝试编写一个只返回第一个可能解决方案的数独求解器.我设法用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
}

任何帮助将非常感谢.

Answer 1

这是大多数递归回溯问题的伪代码.

如果您已经在解决方案,请报告成功.

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;
}

你只需要实现一些非常简单的方法.