Most effecient way to compute a series of moves in peg solitaire.

Question

Given an arbitary peg solitaire board configuration, what is the most effecient way to compute any series of moves that results in the "end game" position.

For example, the standard starting position is:

..***..
..***..
*******
***O***
*******
..***..
..***..

And the "end game" position is:

..OOO..
..OOO..
OOOOOOO
OOO*OOO
OOOOOOO
..OOO..
..OOO..

Peg solitare is described in more detail here: Wikipedia, we are considering the "english board" variant.

I'm pretty sure that it is possible to solve any given starting board in just a few secconds on a reasonable computer, say an P4 3Ghz.

Currently this is my best strategy:

def solve:
    for every possible move:
        make the move.
        if we haven't seen a rotation or flip of this board before:
            solve()
            if solved: return
        undo the move.

Answer 1

The wikipedia article you link to already mentions that there only 3,626,632 possible board positions, so it it easy for any modern computer to do an exhaustive search of the space.

Your algorithm above is right, the trick is implementing the "haven't seen a rotation or flip of this board before", which you can do using a hash table. You probably don't need the "undo the move" line as a real implementation would pass the board state as an argument to the recursive call so you would use the stack for storing the state.

Also, it is not clear what you might mean by "efficient".

If you want to find all sequences of moves that lead to a winning stage then you need to do the exhaustive search.

If you want to find the shortest sequence then you could use a branch-and-bound algorithm to cut off some search trees early on. If you can come up with a good static heuristic then you could try A* or one of its variants.

Answer 2

Start from the completed state, and walk backwards in time. Each move is a hop that leaves an additional peg on the board.

At every point in time, there may be multiple unmoves you can make, so you'll be generating a tree of moves. Traverse that tree (either depth-first or breadth-) stopping any branch when it reaches the starting state or no longer has any possible moves. Output the list of paths that led to the original starting state.