Peg Solitaire can't find a solution with backtracking

Question

I'm working on a solution for the game Peg Solitaire in Java. It appears however, that my solution is unable to solve the game.

I'm working with the 'standard' version, so the board looks like :

{2, 2, 1, 1, 1, 2, 2}
{2, 2, 1, 1, 1, 2, 2}
{1, 1, 1, 1, 1, 1, 1}
{1, 1, 1, 0, 1, 1, 1}
{1, 1, 1, 1, 1, 1, 1}
{2, 2, 1, 1, 1, 2, 2}
{2, 2, 1, 1, 1, 2, 2}

0 is empty, 1 is a peg, 2 is nothing

The desired state of the board is

{2, 2, 0, 0, 0, 2, 2}
{2, 2, 0, 0, 0, 2, 2}
{0, 0, 0, 0, 0, 0, 0}
{0, 0, 0, 1, 0, 0, 0}
{0, 0, 0, 0, 0, 0, 0}
{2, 2, 0, 0, 0, 2, 2}
{2, 2, 0, 0, 0, 2, 2}

My solve() method works like this:

move peg on location x,y in a direction (up, down, left or right)
check if the board is in the desired state, if so, print board and moves taken and exit the program
Check if there is a still a peg that can be moved, if there isn't one exit the function
Find the first possible peg that can move in 1 or more directions; call solve() for that peg and it's direction.
(if we get here step 4 produced a undesired board state) undo the move made in step 4 and recall step 4 with the next possible move that peg could make, if any.
return to step 4 for the next possible peg that comes after the peg found in step 4.

I've implemented the above instructions like this:

private void play(int xx, int yy, Direction direction) {
    board.move(xx, yy, direction);

    if (board.finished()) {
        board.printBoard();
        System.out.println(moves);
        System.exit(0);
    }

    if (board.noMoreMoves()) {
        return;
    }

    for (int y = 0; y < board.board.length; y++) {
        for (int x = 0; x < board.board[y].length; x++) {
            if (board.containsPeg(x, y)) {
                Direction[] moves = board.getMovesFor(x, y);

                for (Direction move : moves) {
                    if (move != null) {
                        this.moves++;
                        play(x, y, move);

                        if (move.equals(Direction.UP)) {
                            board.undoMove(x, y-2, move);
                        } else if (move.equals(Direction.DOWN)) {
                            board.undoMove(x, y+2, move);
                        } else if (move.equals(Direction.LEFT)) {
                            board.undoMove(x-2, y, move);
                        } else if (move.equals(Direction.RIGHT)) {
                            board.undoMove(x+2, y, move);
                        }
                    }
                }
            }
        }
    }

    return;
}

However, the above solution does not produce the desired board state. I have this version running in eclipse for over an hour now, without any results.

I've tested the methods board.move(x, y, direction), board.finished(), board.noMoreMoves(), board.containsPeg(x, y), board.getMovesFor(x, y) and board.undoMove(x, y, direction) in isolation and they all appear to function as desired.

Is there something I'm missing here, either in my implementation or in recursion / backtracking in general? I'm pretty sure the solution doesn't require over 200 million moves to be made.

There are 32 pegs initially. Every move should remove one peg from the board, and there's certainly no valid move to do if there's only one peg remaining, so you definitely should never get the recursion deeper then 31 levels. Are you sure board.move() removes a peg? — CiaPan

arcy arcy · Accepted Answer · 2013-04-07T00:03:07

What you need is a debugging strategy.

Use a method that will output the state of your board. Also write one that will save a representation of your board, and one that will compare two states to see if they're the same.

Output after the first method has failed, then at different points after backtracking to ensure that the backtrack has backtracked back to the right track.

Also make sure that you aren't tracking the same move more than once.

As for the possible number of moves, don't be too sure. One wouldn't think, a priori, that there were billions of possible moves in the first 10-20 moves of chess, but there are.

Peg Solitaire can't find a solution with backtracking

1 Answers