4

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?

Josh
  • 366
  • 2
  • 8
  • 20
  • 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 Oct 17 '14 at 09:17
  • Could you add logging to the different steps to see where it gets into an infinite loop? – Kurt Du Bois Oct 17 '14 at 09:20
  • @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 Oct 17 '14 at 09:26
  • @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 Oct 17 '14 at 09:26
  • How is your program's time complexity? basically, I believe that your program just have a very big time complexity, which cause your program can only finish in hours (or even life time). – Pham Trung Oct 17 '14 at 09:30
  • @PhamTrung I don't think this is the case, since every possible path to a solution (or incorrect paths) should be explored on an unsolvable board, in finite time (and indeed not very much time for such a small board). Time complexity is in fact what I intent to investigate once my solution works properly. – Josh Oct 17 '14 at 09:34
  • 1
    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 Oct 17 '14 at 09:37
  • can you scale your board down, thats should reduce number of possibilities and makes easier go track potential error – user902383 Oct 17 '14 at 10:12
  • @PhamTrung After giving it some more thought, I think perhaps you are correct. This would mean there is nothing wrong with the algrorithm, and its just taking too long – Josh Oct 17 '14 at 10:13
  • huge problems in terms of configurations to be tested may not be infinite in the mathematical sense, though they can be in the factual sense. A problem with factual infinity is a working genetical arrangement for the culture, eg. in mammals, incl man. explicit search does not help. In the case of natural evolution (I don't talk about genetic algorithms here) there are many tricks: Use of dynamic cost functions and a multi-layered memory (in terms of size and time) are only two of them. The ultimate cost is that you won't be sure whether there is a "better" solution, but at least you get one. – monnoo Nov 12 '14 at 17:59

1 Answers1

0

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.

Topological Sort
  • 2,733
  • 2
  • 27
  • 54