We still need a few more things to implement the algorithm above.įirst, the list of valid moves. That peg is removed from the set of pegs when the game begins. The constructor takes a parameter called missing to indicate which peg was picked to be blank.
Wrapping that all in a class gives to following code: class Triangle5(object): A list is used to keep track of moves made to get to the state the board is in. Game state can be represented by a set of occupied pegs. The first number is the source hole, the second is the jumped hole, and the last number is the destination hole. I’m choosing Python to solve this in, so each jump will be represented by a 3-tuple. To implement this solution, we’ll need a list of all possible jumps on the board. In order to identify each hole, I chose to start at 0 and increase left to right, top to bottom to 14. Therefore, the first solution found is just as good as any other in terms of length. As it turns out, every solution is exactly 13 moves, since 1 peg is removed each time and there are 14 pegs to begin. Since you want to be able to reproduce your success and show off to your friends, you also might want to keep track of the moves you have made on the way to the solution.ĭoes this produce the optimal solution? Maybe the first solution found isn’t the shortest.
This algorithm is essentially Depth First Search. If you’ve tried all moves and not found a solution, then one must not exist. If you have no moves left but haven’t won, undo the move you just made and try a different one. If you then have one peg left then you have won. The simplest way to solve the game would be to make a valid move, then make another valid move, and keep going until there aren’t any moves left. This means no fancy puzzle-solving or constraint techniques are probably going to be needed. For a computer, that’s practically nothing. A hole can be occupied or not and there are 15 holes for 2 15 states. Is such a thing possible? Let’s consider the number of possible game states. So let’s see if we can write a program to solve it for us.
#PEG SOLITAIRE ALGORITHM JAVA CRACKER#
The jumped peg is then removed from the board.Įven with these simple rules and my many visits to Cracker Barrel, I hadn’t ever solved it down to one.
A jump consists of picking up on peg, moving over another peg, and placing it down in an empty hole.Pegs can be elimated by jumping one peg over another.The goal of the game is to eliminate all but 1 peg from play.The choice of this hole is up to the player.One hole is open at the beginning of every game.There are 14 pegs that are placed in a triangle made of 15 holes.If you haven’t played it before, the rules are fairly straightforward. If you’ve ever been to a Cracker Barrel restaurant, you’ve probably played this game: Cracker Barrel Peg Game.
0 kommentar(er)
