钉接龙回溯无限循环 [英] Peg Solitaire backtracking infinite loop

问题描述

我正在用Java回溯制作钉式单人纸牌解析器.

I'm making a peg solitaire resolver with backtracking in java.

这是我做过的方法:

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 .如您所见，解决方案数组不完整.

The problem is that I can't find the solution. Here is the output of the code: http://pastebin.com/raw.php?i=BhkLu3qr. As you can see the solution array is incomplete.

谢谢.

推荐答案

假设您的board.getMovements()方法为您提供了游戏到此位置的所有可能动作的列表，那么您就差不多了.获胜时，您只需要停下来.为了清楚起见，我进行了一点重构.

Assuming that your board.getMovements() method gives you a list of all possible moves from this point in the game, you're almost there. You just need to stop when you win. I've refactored at bit for clarity.

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

这篇关于钉接龙回溯无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！