In the peg puzzle, this is not the case: although there are duplicate states, no move will ever lead to itself again and so there is not risk of falling into loops. Regarding completeness, naive DFS in most search spaces can easily end up getting trapped in loops around the same states. Upon more careful inspection this is due to the fact that the heuristics that are being used are extremely poor predictors of performance.Īpplying DFS to the peg puzzle is especially effective due to the fact the nature of the puzzle solves most of the ‘problems’ that typically emerge in dealing with DFS: namely completeness and optimality. In actuality though, the opposite it true: A* found a solution only marginally faster than BFS, and was several factors of magnitude slower than uninformed DFS. It occurred to me that the heuristics that we were testing with were not ideal, but I had presumed that they would manage to find a solution at least as quickly as DFS. What I had not anticipated was how poorly A* and IDA* performed. I had anticipated that it would perform far better than breadth first search (BFS): all the available solutions occur at depth 13, and they are fairly numerous.
Of all the search strategies, depth first search (DFS) performed the best by far. The basic solitaire puzzle on a 33-cell board - to begin with a single vacancy in the center and to finish with a single peg in the center - requires 32 jumps, which can be grouped into 18 moves.Written using Python3.4 with numpy 1.9.2 Analysis of Search Strategies
#Peg solitaire solutions series
However, a series of consecutive jumps made at one time with a single piece can be regarded as a single move hence a player can aim not merely at solving a given puzzle, but also at finding the solution that requires the smallest number of moves. The number of jumps made in a game of solitaire equals the number of pegs removed.
The player is required to finish the game with a single peg in the central cell. All cells are filled except the one in the center. "In the most widely known solitaire puzzle the 33-cell board is used. There are two kinds of boards used for peg solitaire.Īnother eliminates the corner cells, forming a cross-shaped pattern of cells (top right diagram). Jumps can be made only along the lattice lines (as shown in the diagram) a peg cannot jump diagonally." Following such a move, the peg over which the jump was made is removed from the board. There are many games and puzzles that can be devised for the solitaire board, but the method of making moves is common to all of them.Ī peg (assuming that this is the marker used) can be moved only by jumping it over a neighboring peg to a vacant space directly on the other side. His new invention, like the earlier game, used a board in which an array of holes - called cells - were bored as resting places for pegs or marbles. He was modifying an already existing game called Fox and Geese. "According to one old story, the game of peg solitaire often called simply solitaire, was invented in the 18th century by a French nobleman imprisoned in the Bastille, the grim fortress-prison in Paris. īy authors Pieter van Delft and Jack Botermans: The following quote is taken from the book Creative Puzzles Of The World. with many links to other internet areas which help supplement his wealth of information. For a great in-depth scientific notation on peg solitaire puzzles - and history, one can view my good friend, George Bell's website here.