如何通过此回溯找到第一个解决方案 [英] How to find the first solution only with this backtracking

问题描述

我正在尝试编写一个只返回第一个可能解决方案的数独求解器。
i设法用void方法打印所有可能的解决方案，但我不能在第一次找到时停止。

i'm trying to write a Sudoku solver which will return only the first possible solution. i managed to print all possible solutions with void methods but i can't stop on the first find.

我知道首选的方法是切换到布尔方法并返回 true 向上树 -
但我找不到合适的方式来写它。

i know the preferred way is to switch to boolean methods and return true up the tree - but i can't find the right way to write it.

我尝试的任何方式总是给出编译错误（方法必须返回布尔值）。

any way i tried always give compilation errors (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
}

任何帮助都将非常受欢迎。

Any help will be most appreciated.

推荐答案

以下是大多数递归回溯问题的伪代码。

Here is some pseudocode for most recursive backtracking problems.

如果您已经在解决方案中，请报告成功。

If you are already at a solution, report success.

for（当前位置的所有可能选择）{

for (every possible choice in the current position ) {

做出选择并在路径上迈出一步。

Make that choice and take one step along the path.

使用递归从新位置解决问题。

Use recursion to solve the problem from the new position.

如果递归调用成功，则将成功报告给下一个更高的
级别。

If the recursive call succeeds, report the success to the next higher level.

退出当前选择以恢复循环的
开头的状态。

Back out of the current choice to restore the state at the beginning of the loop.

}

报告失败。

以下是一些基于斯坦福大学讲座的实际代码。我在java中重写它并包含注释。

Here is some actual code based on a lecture from Stanford. I re-wrote it in java and included comments.

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

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

You just need to implement a few methods, which are pretty trivial.

这篇关于如何通过此回溯找到第一个解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！