If this recursion returns true, then a solution was found.If so, make the move, and call the function again on a "new" version of the game board, with this move made.If not, iterate to the next possible move.Check and see if the positions currently house a PPH pattern.For every move in the list of possible moves,.Now that I have described how the program works, here is a loose description of how the algorithm works: In this case, the word search approach may be more feasible, as it is easy to define define the board shape in the grid by simply setting locations outside of the board to a character that will not be matched. The numbering of the peg/hole locations corresponds with the table of possible moves. Additionally, the way that the game board itself is represented will have to be changed slightly, but this translates to expanding the size of the array. However, this was a manual process for me. If this process can be automated (perhaps by finding a pattern), this becomes less of an issue. Naturally, due to this design, applying this technique to bigger boards or boards of different shapes will increase the list of all possible moves by a large amount, which is tedious to determine beforehand. For example, referring back to the number-based board, represents a valid move as a peg at position 1 can jump over a peg at position 2 to arrive in the hole located at 4. Valid moves are created by finding the (legal) jumps where you can transform a PPH into a HHP pattern. Take the triangular board, and number it from 1 to 15. The method I eventually settled on can be thought of as heap-like. This is actually a horrible idea, I think, but I thought of this initially when I was trying to come up with a plan. Finding valid moves is as simple as trying to search the grid for a PPH pattern, with P representing pegs and H representing holes. If you think of it that way, half of a grid can represent the triangular board. There are a few ways the board can be represented: The biggest challenge for me when I first picked up this exercise, aside from the backtracking itself, was how to represent the game board. Java (original implementation language this repository).This program has been implemented in various languages: It is an exercise in the algorithm technique known as backtracking. Puzzle Pegs is a program that solves the 15-hole triangular peg solitaire game, also known as the peg game from Cracker Barrel.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |