Peg Solitare Recusion solution

Everyone knows of the cracker barrel triangle peg solitare 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?

And 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.

Keep in mind 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 know I'm a bit vague, I'm only expecting pseudo code answers. Pseudo code alone is enough to put me on the right track. I'm coding in Java if that makes a difference.

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.

Category:algorithm Views:0 Time:2018-02-13

Related post

• How to create a program that solves a Triangular Peg solitare - C++ / Java programming? 2011-09-29

Honestly, I only knew of such a game recently and I wonder how one can create a solving algorithm using the recursive search method? There are 15 holes in total in the triangular board. Making that 14 pegs with a total of 13 moves. I don't know where

• Identify this Algorithm: Slots and Pegs 2009-02-06

I have a number of slots and pegs arranged in a straight line. The pegs can be moved and need to be moved to a slot each. A slot can be left empty only if all pegs are taken. When a peg is moved, it is not allowed to go past another peg. In other wor

• Android "cpu may be pegged" bug 2011-12-10

Foreword: This severe bug can cause Android devices to lock up (unable to press Home/Back buttons, needs hard reset). It is associated with OpenGL surfaces and audio playback. Logcat repeats something to the effect of W/SharedBufferStack( 398): waitF

• recursive solution not working as intended/ running into errors 2012-02-08

I'm looking for some help on a problem that I vaguely inquired about before, which is solving 15-peg solitaire recursively. I keep getting strange errors when I compile and run it, most of them say "stack overflow" or that I'm getting a seg fault. Th

• Where can I find a driver for Sony PEG TJ37? 2012-07-23

Original Title:PEG TJ37 need a driver for windows vista for sony clie PEG TJ37 --------------Solutions------------- hi contact Sony for any available Drivers for their Products they write them, not Microsoft http://esupport.sony.com/perl/select-syste

• How can I get sound back in Solitare? 2014-01-03

How do I get the sound back after winning a game of Solitare? --------------Solutions------------- Hi JerryAn99, 1. Do you get sound while playing the game? 2. Did you make any changes on your computer prior to this issue? 3. Do you get the default W

• Using a word list with wildcards in SQL Server stored proc 2011-06-28

I have a list of words that I want to exclude from some query results. The list of words is stored in a database table as a comma separated list. eg. bad, awful, worst. (Note: It isn't important that they are comma separated. They could just as easil

• Parsing unordered sequence with parsing expression grammar 2011-07-17

Is there a (simple) way, within a parsing expression grammar (PEG), to express an "unordered sequence"? A rule such as Rule <- A B C requires A, B and C to match in order. A rule such as Rule <- (A B C) / (B C A) / (C A B) / (A C B) / (C B A) /

• Python Workflow Design Pattern 2011-10-26

Im working on a piece of software design, and im stuck between not having any idea what im doing, and feeling like im reinventing the wheel. My situation is the following: I am designing a scientific utility with an interactive UI. User input should

• refere to full version in my app 2012-02-06

I tried to submit my app on appstroe , it's a free version and I already have full version, I want to mention on the new app to the full version I have three tabs when the user click on tab I need him/her to be directed to the full version on appstor

• Available labels by vendor and type 2012-05-25

Is there a way to print out the available labels by vendor and their label types in Word? Thank you. Peg Lundquist --------------Solutions------------- Select the label, edit the text and print. Click Mailings > Labels > Labels tab > Options

• 2007 Outlook does not clear the OUTBOX 2012-06-05

What i've learned so far re my problem is that the OUTBOX does not clear/empty when replying to certain emails sent to me. Now, the curious thing is that this does not happen to all emails that i reply to, just certain ones. I sure appreciate all the

• After installing Windows 8, I can't find the Games from Windows 7 2012-06-24

I just installed Windows 8 upgrade on my new Lenovo which came with Windows 7. I don't have, or can't find the games which were in "accessories" on Windows 7. I am specifically talking about free cell, solitare and spider solitare. --------------Solu

change the ads on windows 8 solitare app --------------Solutions------------- Hi, Thank you for reaching Microsoft Community forums. I would suggest you to contact Xbox support for better assistance on this query. Xbox Support http://forums.xbox.com/

• how to re installing standar windows game 2012-10-10

how to re installing my windows games,free cell,solitarie,spider solitarie. --------------Solutions------------- From Control Panel - Add or Remove Programs - Add/Remove Windows Components If it shows that they are already installed then... Uninstall

• porque nao conseguimos acessar as pastas que estão armazenadas no sd e na memoria interna do nokia lumia 620? 2012-12-16

porque não conseguimos acessar as pastas que estão armazenadas no cartão sd e na memoria interna do Nokia lumia 620? e o flash player e bastante útil. radio fm também não pega. --------------Solutions------------- Hi, Please select your language by c

• Apps/Tiles won't work after update. 2013-11-21

I've had my laptop for about two weeks now and when I go to open apps/tiles they go to the full screen icon then goes back to the start menu. The only apps that work are games(solitare & mahjong) --------------Solutions------------- Hi BrenM1996,

• Microsoft games not executable such Mahjong Titans, Chess & Solitaire 2014-07-03

Original title : Games Why are our microsoft games not excutable such Mahjong Titans, Chess,Solitare --------------Solutions------------- Hi bobfranksYX, Thank you for posting in the Microsoft Community. I’m sorry to know that you are facing issue Wi

• Please lend a hand......! 2015-02-22

I was given a microsoft kybrd 3000 model @1066 part# X806594-001. I also have the s/n & prod. id# if you need them. A friend helped me out by giving me this keyboard. It is wireless and I am kinda bedridden most days. I cannot locate any download

• Are we as developers trying to put a square peg into a round hole with REST any other solutions? 2011-12-28

Recently I was tasked to take an old web service pre SOAP/REST era and bring it up to par with current web service "standards". It's pretty straight forward service, HTTP(s) POST XML, do stuff and respond with XML a very message oriented service. The

• after clicking on spider solitare, I get a message Failed to create Directx device. Can't find a solution anywhere. 2012-09-01

After clicking on spider solitare, I get a message that says Failed to create Directx device. Can't seem to find a solution anywhere. This game is played more than any other game on my computer. Never had a problem before. --------------Solutions----

• Are there any Parsing Expression Grammar (PEG) libraries for Javascript or PHP? 2008-09-17

I find myself drawn to the Parsing Expression Grammar formalism for describing domain specific languages, but so far the implementation code I've found has been written in languages like Java and Haskell that aren't web server friendly in the shared

• Delegate calling generic method inside of a generic class pegs CPU during deserialization 2008-11-06

Has anyone else run into this problem before? I've got a method that calls a generic method with a delegate, inside of a generic class. I've marked the class as Serializable, and it serializes without complaint. But, when I try to deserialize an obje

• System.DirectoryServices pegs my processor when multi-threaded - can I lower the burden? 2009-02-23

My application takes the currently logged-in user and uses an a DirectoryServices.DirectorySearcher to pull a few additional detail about them (some properties we have stored in a few custom AD fields, as well as their email address). This works grea