Peg纸牌回溯无限循环

Question

我正在用java制作一个带回溯功能的peg纸牌解析器。

我就是这么做的：

private void solve(Board board, ArrayList<Movement> solution, Boolean result) {
    ArrayList<Movement> movs = board.getMovements();
    for (Movement movement : movs) {
        if (board.isMovementValid(movement)) {
            board.doMovement(movement);
            if(!board.isSolution()) {
                solution.add(movement);
                solve(board, solution, result);
                result.setValue(false);
            } else {
                result.setValue(true);
            }

        }
    }
    result.setValue(false);
}

问题是我找不到解决办法。以下是代码的输出：http://pastebin.com/raw.php?i=BhkLu3qr.如您所见，解决方案阵列不完整。

谢谢

Answer 1

假设你的board.get运动（）方法给你一个列表，列出了游戏中从这一点开始的所有可能的移动，你就快到了。你只需要在赢的时候停下来。为了清楚起见，我已经重构了一点。

private boolean solve(Board board, ArrayList<Movement> solution) {
    // The base case: if it's already solved, we're done
    if (board.isSolution())
        return true;

    // Get all possible moves from this point
    ArrayList<Movement> movs = board.getMovements();
    for (Movement movement : movs) {
        if (board.isMovementValid(movement)) {
            board.doMovement(movement);
            solution.add(movement);
            if (solve(board, solution))
                // That move led to success :-)
                return true;
            else
                // That move led to failure :-(
                solution.remove(movement);
        }
    }
    return false;
}

Answer 2

虽然不那么优雅，但为了回溯并重试替代方案，必须返回以下步骤：

ArrayList<Movement> movs = board.getMovements();
for (Movement movement : movs) {
    if (board.isMovementValid(movement)) {
        board.doMovement(movement);
        solution.add(movement);
        if(!board.isSolution()) {
            solve(board, solution, result);
            // Initialized to result.setValue(false);
            if (result.getValue()) { return; }
        } else {
            result.setValue(true);
            return;
        }
        solution.remove(movement);
        board.undoMovement(movement);
    }
}
result.setValue(false);

此外，对于更一般的解决方案，如果您对第一个解决方案感到满意，我还添加了回报。