How to solve peg solitaire with a graph search?

Question

Problem

I've been reading research papers on how to solve a peg solitaire using graph search, but all the papers kind of assume you know how to do the reduction(polynomial time conversion) from the peg solitaire to the graph, which I do not, but this is how I assumed it was done.

For those of you unfamiliar, here is a video that illustrates how to play this game, and here's an image of a board.

The goal is to only have one peg on the board and you get rid of pegs by jump one peg over another. A peg can only jump if the it's jumping into an empty space as shown in the picture above.

What I've tried

I had the idea of converting the problem to a tree where each node represents the state after an action is taken and each edge represents the action taken. So the root node would the initial state which is the board shown above then it's children would be the state of the board after any of the possible legal actions that can be taken.

So, for example:

Then the children of each of those nodes would be the possible moves for them and you can find a solution once you've reached depth 31 in the tree because there are 32 pegs and you win the game where there's only 1 left.

Is this the right approach? It feels a little too abstract because I'd have to represent the edges as peg moves, but that's weird cause they're usually numbers or constraint.

Answer 1

Your approach seems reasonable to me. The edges do not necessarily have to be numbers, but, if you wish, you could also encode the actions as numbers. For example, the weight of an edge could represent the "cost" of the corresponding action. If there's no natural cost associated with an action, then you can add a unit cost for each action.