java - 返回静态、递归 Java 方法不起作用

Question

我尝试实现一个数独求解器。我正在调用 printSoluition(board) 方法，它应该打印出解决方案(如果存在或为空)。

我正在尝试一个有一个解决方案的示例。但它总是返回 null。

我的代码:

static void printSolution(SudokuBoard board) {

    SudokuBoard resultBoard = findSolution(board);

    if(resultBoard != null) {
        resultBoard.print();
    }
}

static SudokuBoard findSolution(SudokuBoard board) {

    if (board.isSolved()) {
        return board;

    } else {

        int nextEmptyField = getNextFreeIndex(board);

        if (nextEmptyField != -1) {

            int[] kandidaten = board.getCandidates(nextEmptyField);

            for (int i = 0; i < kandidaten.length; i++) {

                SudokuBoard newBoard = board.set(nextEmptyField,
                        kandidaten[i]);

                return findSolution(newBoard);
            }
        }

        return null;
    }
}

Answer 1

您的回溯实现递归是不正确的，因为您的 for 循环永远不会越过第一个候选者。

您需要将循环更改为仅在找到解决方案时才返回:

for (int i = 0; i < kandidaten.length; i++) {
    SudokuBoard newBoard = board.set(freiesNaechstesFeld, kandidaten[i]);
    SudokuBoard solution = findSolution(newBoard);
    if (solution != null {
        return solution;
    }
}

现在所有调用级别的所有候选项都将被尝试，因此最终您将得到一个解决方案(当然，假设您的“帮助程序”方法可以很好地查找和设置候选项)。