Peg Solitaire backtracking infinite loop

Question

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

This is the method I've done:

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

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.

Thanks.

So where's the backtracking part? – Erick G. Hagstrom Oct 24 '15 at 10:39 — Erick G. Hagstrom, Oct 24 '15 at 10:39

score 0 · Answer 1 · answered Oct 24 '15 at 10:42

Not so elegant, but in order to track back and retry an alternative the step must be taken back:

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

Also for a more general solution where you are satisfied with the first solution, I have added returns.

I do not know the logic to separate dones from todo candidates. Maybe `solution.remove(movement)` is wrong. Look into other backtracking samples/tutorials to get inspiration. — Joop Eggen, Oct 25 '15 at 12:29

score 0 · Answer 2 · answered Oct 25 '15 at 14:26

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

Peg Solitaire backtracking infinite loop

2 Answers2

Linked