For peg solitaire, the usage of bit-boards is especially easy, since each hole can either be empty (binary 0) or filled with a peg (binary 1). One major improvement of a classical algorithm can be achieved when instead of arrays, so called bit-boards are used for representing a position. Without the utilization of some advanced approaches, an algorithm could run for many days until a solution is found. Also for backtracking algorithms the computational effort is enormous in order to solve this problem. Since there are many corners on this board it is rather difficult to find a solution where only one peg is left over in the end. In the beginning, only two moves are possible. As I was told – in contrast to the English variant – the only initial empty hole is not located in the center of the board but has to be placed at a slightly different position in order to be able to solve the game (as I found later, the solver was not able to solve the game for an initially empty hole in the center of the board). Efficiently Solving the Diamond-41 BoardĪs the name suggests, the Diamond-41 board consists of 41 holes. This stirred my interest in the game again and I spent several hours writing a solver using bit boards and some other enhancements for this board, as described in the following section. Recently, I again stumbled across peg solitaire when I saw a different board with the shape of a diamond.
The solver gave me the following solution: With a slightly adjusted move ordering the solver apparently needs much more time (several hours). I suppose that I was actually quite lucky with the standard move ordering that I was using. It is not nice nor efficient, but surprisingly finds the solution in less than a second.
#Solitaire peg board game rules code#
The code is attached at the end of this post. Since I could never solve the game myself I decided to write a solver for the problem. When I started programming a few years ago, English peg solitaire was one of my first projects. The solution for the diamond shaped board is even more tricky. Many players need quite a few attempts in order to find the solution for the English peg solitaire. The English variant is shown in the figure below.Įven though the rules of the game are rather simple, finding a solution is not trivial. The English variant, as shown below, has one additional rule: In order to win, it is not sufficient that only one peg is left in the end this peg also has to be located in the center of the board. This is the case when there is no pair of pegs which are orthogonally adjacent or if only one peg is left. Once no move is possible any longer, the game is over. So, in each move, one peg jumps 2 holes further and the peg in-between is removed. The neighboring peg is then removed, leaving an empty hole. In each move the player selects one peg and jumps – either vertically or horizontally, not diagonally – with this peg over a directly neighboring one into an empty hole. For example, the English variant consists of 33 holes while the typical diamond variant consists of 41 holes. The number of holes depends on the board variant. Peg solitaire is a one-player game played on a board with holes and pegs. Many of us might now the board game peg solitaire and might even have one of its many variants at home. Interestingly, it has been deduced that the 37 point board is less complex than the 33 point board.Solving Peg Solitaire with efficient Bit-Board Representations You can also aim to get certain patterns of pieces left over. Once you have mastered the basic game, target a different hole as the hole that the final piece should finish in. Therefore, the first turn can be made only by jumping a piece into the middle hole from one of 4 possible points. The player makes successive capturing moves, removing a single piece each turn until is it impossible to make any more capturing moves.Įach turn, the player captures a piece by jumping over that piece orthogonally (not diagonally) from one adjacent point to the vacant adjacent point on the other side. Solitaire is played by one person and is therefore technically not a game at all, but a puzzle. The objective is to remove every piece except one, with the final piece ending up in the centre hole. The game is set up so that pieces fill every hole except the middle hole. Solitaire can also be played on other shapes of board - two of the most interesting are a 41 point board (take the 33 point board and add 3 extra points at the 4 ends of the cross) and the 45 point board (take the 37 point board and add a single point in the middle of each of the 4 square ends - to makes a square). In France and Sweden a 37 point board is more common with 36 pegs, marbles or pieces. The game of Solitaire is most commonly played on a 33 point board (as pictured above left) in a cross shape with 32 pegs, marbles or pieces. It’s the French and Swedish version of ( Peg) Solitaire.
0 kommentar(er)
