Recursive backtracking algorithm not solving some cases

Question

I am currently programming a recursive algorithm to solve a game of Peg Solitaire.

The algorithm needs to use the "backtracking" approach to solve the board. I think I have managed to get a very close to correct solution. It seems that my code correctly solves the board for all solvable boards. It also seems to correctly determine when a board is not solvable, but only when the number of pegs isn't too high.

My recursive method looks like this:

public static void solve()
{
    if(isSolved())
    {
        long endTime=System.currentTimeMillis();
        System.out.println("Solved");
        solved=true;
        printArr(board);

    }
    else
    {
            for(int i=0;i<7;i++)
            {
                for(int j=0;j<7;j++)
                {
                    for (int k=0;k<4;k++)
                    {
                        if(makeMove(new int[]{i,j,k}))
                        {
                            if(solved!=true)
                            {
                                solve();
                                undoMove();
                            }
                        }


                    }
                }
            }
        }
    }

The board is a standard Peg Solitaire board. I am confident that my isSolved() method correctly determines whether the board is solved. My makeMove function takes in a row, column and direction (i, j and k). It finds the peg at those coords and checks if it can move it in the requested direction. If it can, it makes the move, adds the move to an array of moves, and returns true. If not, it returns false.

My undo method pops the last move off of the array and reverts the board to its previous layout (before the popped move was made).

It seems that for random boards with around 25 pegs or more, the program simply won't terminate. It continues processing indefinitely. Solvable boards and various unsolvable boards with less pegs seem to consistently terminate within 10 seconds with the correct result.

Any Ideas?

Is it possible your algorithm just takes a very long time or performs two moves that do not change the state of the game? I.e. move card A to stack B and then move it back? — MrHug
Could you add logging to the different steps to see where it gets into an infinite loop? — Kurt Du Bois
@MrHug The algorithm technically tries every "path" to a solved board until either one is found, or a specific "path" reaches an unsolvable board, at which point that recursive series of method calls terminates, and undoMove() is called. The process then repeats from the next available point on the board, so I can't see how it could get stuck. — Josh
@KurtDuBois, I've tried something like that but the logging seems quite useless since the board continues to change (in fact all of my solvable boards often take 300 000+ undoMove calls before it arrives at a solutions so its hard to reckognise an infinite loop — Josh
Can you show your full code? try every permutation for a board size of 7*7*4 is (7*7*4)! , which is very huge — Pham Trung

Topological Sort Topological Sort · Accepted Answer · 2014-11-12T15:54:39

Since every move in peg solitaire removes a peg, you can't possibly be looping back to a previous state: say, as in simple path planning, where a robot could be moving back and forth between two squares forever. So that's not it.

So is your algorithm wrong? Here it is, reduced for simplicity:

solve (board state) is

if the board is solved, record success
else
   for all possible moves from this board state
      if move is possible
        make it
        call solve
        undo the move

This algorithm can't possibly get you stuck in a loop; when it recurses, it goes deeper into the search space (that is, it makes a move). So that's not it.

It is possible that you have an error in some of the functions you didn't show (make move, undo move). If make move doesn't do anything, your program won't end, whatever the size of the problem.

I'd conclude then that the problem is that a very large search problem can take a very long time. You could play with the problem size. If it works for a problem of size N, does it work for one of size N+1? Taking a few seconds to solve one of size N suggests that you can forget getting it to solve N+10 (I say, based on experience of a similar problem): not just because it's an exponential problem, but because you may get thrashing as the system tries to get enough memory.

Sometimes a solution is to keep track of nodes you've already tried, to reduce redundant search. I suspect you won't get much help on this problem -- you can't keep a list of visited states (it would take exponential memory), and keeping a list of visited states for the first few levels won't expand the depth to which you can search by that much.

This is all in aid of the conclusion others have reached: it's just a big problem.

Recursive backtracking algorithm not solving some cases

1 Answers