Java递归数独求解器，递归函数不返回正确值

Question

我正在使用数独解算器，但无法正确返回/结束解算器功能。 moveOn() 函数中的 show() 被调用，它会很好地显示已完成的数独，但solve 返回 false。我试图在问题解决时让解决返回 true，在无法解决时返回 null，但不知道如何实现这一点。

L 是棋盘的长度(9 x 9 数独的 L = 9)

getSquare(r,c) 返回表示数独板的二维数组中的值

不同的检查函数检查某个值是否适合特定位置。它们不是问题。

show() 函数在控制台中打印出数组，因此它看起来像一个正确的数独板。

我还有一个 isSolved() 函数来检查二维数组，如果它是有效的已解决数独，则返回 true，否则返回 false。我也尝试将其实现到 solve() 方法中，希望使用它返回 true，但没有成功

//This method's only purpose it to call the findNum function on the next location in the sudoku
public void moveOn(int row, int column) {
    //if the previous location was not the last in the row move to ne next cell in said row.
    //if it was the last location in the row, move to the first column of the next row
    if (column + 1 != L) {solve(row, column + 1);}
    else if (row + 1 != L) {solve(row + 1, 0);}
    else {show();}
}

//This method finds a valid number for a specific location on the sudoku grid\
public boolean solve(int row, int column) {
    if (row >= L) {return true;}
    //pass over any numbers that are not empty
    if (getSquare(row, column) != 0) {moveOn(row, column);}
    else {
        //attempt to find a valid number for the location
        for (int n = 1; n <= L; n++) {
            if (checkRow(row, n) && checkCol(column, n) && checkSquare(row, column, n)) {
                // If a number is allowed at a specific location set that location to the number
                setSquare(row, column, n);
                //Begin checking for a solution based on previous numbers changed           
                moveOn(row, column);
            }               
        }
        //If no number is allowed in this space backtrack to the last successful number 
        //changed and reset all locations that have been changed recursively
        setSquare(row, column, 0);          
    }
    //If the puzzle is unsolveable
    return false;
}

非常感谢任何可以帮助阐明这一情况的人。 如果需要更多我的代码/信息，我很乐意提供

示例输入文件:http://pastebin.com/6mSKT3ES

编辑:删除完整代码

Answer 1

solve 函数中只有一个 return 语句，即

return false;

由于这是函数中的最后一个语句，并且是无条件执行的，因此 solve 将始终返回 false，除非引发异常。

要获得实际告诉您是否找到解决方案的返回值，您需要使返回值取决于条件。另外，一旦你找到了解决方案，对于适定谜题，继续搜索就没有意义了。

所以你应该在搜索循环中添加一个条件return true;。为此，您需要知道何时找到解决方案。您将递归包装在对 moveOn 的中间调用中，因此最简单的更改就是向 moveOn 添加返回值:

public boolean moveOn(int row, int column) {
    //if the previous location was not the last in the row move to ne next cell in said row.
    //if it was the last location in the row, move to the first column of the next row
    if (column + 1 != L) {return solve(row, column + 1);}
    else if (row + 1 != L) {return solve(row + 1, 0);}
    else {show(); return true;}  // reached end of grid, solved
}

并在“解决”中使用它:

public boolean solve(int row, int column) {
    //pass over any numbers that are not empty
    if (getSquare(row, column) != 0) {return moveOn(row, column);}
    else {
        //attempt to find a valid number for the location
        for (int n = 1; n <= L; n++) {
            if (checkRow(row, n) && checkCol(column, n) && checkSquare(row, column, n)) {
                // If a number is allowed at a specific location set that location to the number
                setSquare(row, column, n);
                //Begin checking for a solution based on previous numbers changed           
                if (moveOn(row, column)) {
                    return true;       // solved, yay!
                }
            }               
        }
        //If no number is allowed in this space backtrack to the last successful number 
        //changed and reset all locations that have been changed recursively
        setSquare(row, column, 0);          
    }
    //If the puzzle is unsolveable
    return false;
}