Peg solitare recursion solution

Question

Everyone knows of the cracker barrel triangle peg solitaire game. You take one peg and jump it over another into an empty hole and the goal is to have only one peg left.

In my code for the game board object I have a function sCpeg(int a, int b) which changes the peg you are currently using to jump. I connected this to a moves variable for the purpose of solving it. Every time you change the current peg and use it to jump that counts as a move. It's done as a very basic heuristic for what I hope to be a search algorithm: Explore all the possible jumps available with one peg. If a solution is not found backtrack, update the current peg and repeat the process.

When I was writing this idea out it sounds like a perfect example to use recursion on except I don't know how to properly use recursion in this scenario. Between backtracking and updating the current peg I'm lost.

Does all of this sound too complicated? Should I just remove the moves and sCpeg() options and have the search algorithm randomly jump until a solution is found?

Is recursion a good method to solve this puzzle? My jump function currently works by only asking for the position you would want to jump to. I would have to change it to take the start and end position desired for each jump, which is easy enough to change, but I don't know if its better or worse for the algorithm.

This is for a school project so I have to implement an uninformed search and a heuristic search algorithm. Changing my jump() function could potentially affect my heuristic.

I'm coding in Java, but since this is a bit vague I'm only expecting pseudo code answers. Pseudo code alone is enough to put me on the right track. .

Edward Doolittle Edward Doolittle · Accepted Answer · 2015-04-20T08:01:26

Here's the framework of a recursive solution:

// given a board description, outputs solution sequence string, or null if no soln
public String sCpeg(boardDescription bd)
  if bd is solution state, return "" // termination of successful recursion
  for each possible move m
    calculate result of m on bd to obtain newbd
    store result of sCpeg(newbd) in subresult
    if subresult is not null, return m + subresult
  end for
  // if we're here, no move worked -- termination, unsuccessful
  return null

I think that's all there is to it.

There's another framework for these kinds of problems: graph theory. The nodes of the graph are board states. We connect two board states with an arrow if you can get one from the other. Then you search for the shortest path in the graph connecting start to end ... use any standard shortest path in digraph algorithm.

But your recursive idea should work just fine.

Peg solitare recursion solution

1 Answers