Last modified March 1st, 2014
In "ordinary" peg solitaire diagonal jumps are not allowed, and the game seems to lose much of its elegance if they are allowed. It should be noted that triangular solitaire is equivalent to solitaire on a square grid with the addition of diagonal jumps along one diagonal only. Beasley [B1] calls ordinary peg solitaire on a square grid "4move solitaire", while triangular solitaire is "6move solitaire". Solitaire on a square grid where moves are allowed along both diagonals is called "8move solitaire". We will use this notation (unfortunately, our distinction between moves and jumps confuses the issue here, and perhaps we should use 4jump, 6jump, and 8jump solitaire).
It is important to realize that the addition of diagonal jumps changes the position classes, and therefore the possible single vacancy to single survivor problems that can be solved. In 8move solitaire, there is only one position class! All boards are nullclass and in general it is possible to play from an initial vacancy to a single peg anywhere on the board.
In 8move solitaire it is possible to start with a single vacancy anywhere on the board and play to finish anywhere else on the board.
Beasley states with this solution "I suspect this can be improved." This solution, with 6 diagonal and 10 "normal" moves, gives an idea of the bizarre and rather nonintuitive moves that can prove useful.
In 2007, I took on the challenge of finding the shortest possible solution with diagonal jumps allowed. With a computer, it seemed it should be easy to beat this solution. However this problem is not as easy as I initially thought. When searching by levels, the number of boards explodes with alarming speed. Also, I came to realize that the above solution is quite good.
However after running my program over night, I was surprised when my program found a
15move solution that looked almost the same as the one above.
In fact, note that the first eight moves and the final move are the same in the solution below:
My program also completed an exhaustive search for a 14move solution, and found none. Hence the 15move solution is the shortest possible, and in fact up to symmetry and move order, there are only four 15move solutions. One of these four is easily obtained by substituting for moves 12 & 13 above the moves c7c5c3 and e7c5. The other two are not simple modifications of the above solution, and do not finish with the move shown above.
My program also found a 13move solution to the c3complement problem
(or equivalently the (1,1) complement problem):
And it was also found that this is the shortest possible. It is interesting that all of these solutions make use of the diagonal loop move: d6b4d2f4d6.
There does not exist any solution on the 33hole board in under 13 moves. This is a conclusion reached from exhaustive computer search.
What is the shortest solution to the central game when moves
are allowed in one diagonal direction only?
Based on the results above, the answer is somewhere between
15 and 18 moves. In this case the square symmetry of the board is lost,
the problem is now diagonally symmetric about both diagonals.
Note that we can also view this problem as a problem in triangular solitaire.
If we put the 33hole board on a triangular (staggered) grid it has a strange appearance:
Nonetheless one can see it is geometrically equivalent, where the original up/down
and left/right moves are diagonal moves on the above board, and the diagonal move that has
been added is a horizontal move.
My program found that the central game under 6move solitaire can
be solved in a minimum of 17 moves, so only one less than normal (4move) solitaire.
There are a large number of 17 move solutions, 413 different sequences of moves
(not counting solutions with the same moves in a different order or equivalent by symmetry).
The longest possible sweep in a solution is an 8sweep, and the diagram
below shows one such solution on the normal board:
Alternately, the same solution may be presented on a triangular
grid, and it looks like:
Although this board is larger than the 33hole board, it is possible to solve it in fewer moves. The figure below shows a solution in only 13 moves. Note that 17 pegs are captured in the first 12 moves, and then 18 pegs are captured in the final 2 moves!
A exhaustive search for a 12move solution was completed, so 13 moves is the shortest possible. There are 1,778 different 13move solutions, not counting solutions equivalent by symmetry or move order.
A resource count which is useful computationally is the one shown below. Unlike most 4move resource counts, the one below is still valid even with diagonal moves. For the central game in the English or French boards, this resource count starts at 8 and finishes at 0. On the English game, the first and last jumps lose 4, leaving only 4 to be lost by the rest of the solution. On the French board, the solution above stays at 8 until the very last move, which loses all 8!
1  0  1  
0  1  1  1  0  
1  1  0  1  0  1  1  
0  1  1  0  1  1  0  
1  1  0  1  0  1  1  
0  1  1  1  0  
1  0  1  
It is possible to solve some problems on the 37hole French Board in only 12 moves, but none in fewer. The c1 and c3 complement problems can be solved in 12 moves:
Let C9 be the board position with only the center 9 holes filled. It is possible to play from this position to any finishing hole on the board. It is also possible to play from the complement of C9 to C9 (this is not possible on the standard 33hole board), thus proving elegantly that one can begin from any vacancy and end at any other board location. The shortest solution from Complement(C9) to C9 has 13 moves, and an example of a minimal solution is given below.
The C9 complement problem is greately restricted by the resource count above, because we cannot make any jump that loses anything by this resource count. It is quite easy to prove that 13 moves is minimal: for we must clear the 8 corners, and this can only fill the holes at {c3, e3, c5, e5}. This leaves us with 5 more vacancies, each of which requires a move, for 13 moves total. In fact, the only way to clear a corner is to end at one of {c3, e3, c5, e5} so for any 13move solution all the moves must end in the central 9 holes.
Shown below is an 11 move solution to the central game. Note the preference for diagonal jumps, especially at the start. The first 8 moves in fact consist only of diagonal jumps. A preference for diagonal jumps at the start seems to be true of all 11move solutions, the reason for this is unknown.
An exhaustive search for a 10 move solution came up empty, so 11 is the shortest possible.
If C9 is again the board position with only the 9 center pegs occupied, then it is possible to play from the complement of C9 to C9. An example of such a solution is shown below. The solution shown below shows that it is even possible to reach the corners from C9. The first row of the solution goes from the top corner vacant to the complement of C9, the middle row goes from the complement of C9 to C9, and the final row goes from C9 to the top corner.
What is the shortest possible solution to the C9 complement? We can prove that at least 13 moves are required: to clear the 4 corners requires 4 moves, and these four moves, can at best fill only one of the central 9 holes. In fact, even to fill the middle hole from a corner will require we supply another peg to the central 9, and we must also fill the remaining 8 empty spots, for 13 moves total. However it seems we cannot even get close to 13, because the shortest solution has 17 moves:
It is somewhat surprising that the central game itself takes only 11 moves, yet the C9 complement, which captures 23 pegs instead of 39, takes so many more moves.
The following resource count is useful in considering the C9 complement:
1  
1  1  1  
0  1  0  1  0  
1  0  1  1  1  0  1  
1  1  0  1  1  1  0  1  1  
1  0  1  1  1  0  1  
0  1  0  1  0  
1  1  1  
1  
Note that for the C9 complement problem, the resource count begins at 12 and finishes at 9, so we can lose only 3. We can also rotate this resource count 90 degrees and obtain a tighter bound. The moves that loses resource count are shown in the above diagram in red (using either the resource count or its 90 degree rotation).
The resource count isn't useful for single vacancy to single survivor problems because the value of the full board is 21, so there is a lot of slack. However, a "Merson Regions" constraint is quite useful in finding minimal length solutions to such problems. It is not hard to demonstrate via exhaustive search with such a constraint, that there is no single vacancy to single survivor problem on this board solvable in less than 11 moves.
In the diagrams below the board is rotated by 45 degrees, this may be confusing if you have played the ThinkFun puzzles. I find it easier to play the puzzle in this way, because all jumps move a frog by two columns, two rows, or both. In the usual orientation it seems a little odd that some jumps move a frog by two "columns", others by four (which is why the ThinkFun puzzles have lines on the board to help denote legal jumps).


If we use
standard 5x5 notation
on this board (central hole is "c3") then the following
single vacancy to single survivor
problems turn out to be solvable:


Standard 5x5 notation  "Hoppers" notation 

The resource count to the left is very useful when playing the Hoppers game. Conceptually, we can think of it as specifying that the removal of a corner frog at {c1, a3, e3, c5} ({A, C, K, M}) requires removal of a frog at {c2, b3, d3, c4} ({D, E, I, J}), and the absence of a frog at the center c3 (G). This is a very useful observation and makes the puzzle much easier. We can prove that certain single vacancy to single survivor problems are not solvable using this argument. For example, if we begin with c2 (D) vacant, the starting value of the resource count is 1, so we can only finish at a hole labeled 1, a corner. Remember, by definition, no jump can increase the resource count. 
The photo below shows one of the "expert" cards from the game. Again the starting value of the resource count is 1, which tells us that
"Downsize", courtesy Gabriel Fernandes 
In fact the same reasoning shows that no single vacancy to single survivor problem on this board can be solved in less than 7 moves.
Note that from the board position before the penultimate move, we can do a single move that finishes at the hole immediately left of the center. This shows that some problems on this board can be solved in 9 moves.
A "Merson region" analysis can be used to prove that no solution to the central game can contain fewer than 10 moves. For this we use 8 regions: the four corners plus four edge pairs. There must be one move originating from each region, and the first and last moves cannot be among these 8.
Central Game Shortest Possible Solutions 

Board  Game  Moves  Number of Solutions 
Longest Sweep 
Comments  


33Hole Board (Standard)  4Move (Normal) 
18  2  5  An 18move solution was discovered by E. Bergholt in 1912. Proved analytically to be the shortest possible by J. Beasley in 1962. Verified computationally. 
33Hole Board (Standard)  6Move  17  413  8  33hole board with moves along one diagonal only, or on a triangular grid. Computational result. 

33Hole Board (Standard)  8Move  15  4  5  33hole board with moves along both diagonals. Computational result. I have been able to prove that this problem cannot be solved in less than 14 moves. 

37Hole Board  8Move  13  1,778  12  The central game is not solvable in 4 or 6move solitaire, because this board is not nullclass. It is not hard to prove that the central game in 6move solitaire cannot be solved in less than 13 moves, and no single vacancy to single survivor problem can be solved in fewer than 12 moves.  
13Hole Diamond Board  8Move  7  7  4  This board is nullclass in 4move solitaire, however no complement problem is solvable. The central game is not solvable in 6move solitaire. For 8move solitaire, it is not hard to prove that no single vacancy to single survivor problem cannot be solved in fewer than 7 moves.  
25Hole Diamond Board  8Move  10  71  10  This board is nullclass in 4move solitaire, however no complement problem is solvable. The central game is solvable in 6move solitaire.  
41Hole Diamond Board  8Move  11  Lots  ≥18  The central game is not solvable in 4 or 6move solitaire, because this board is not nullclass.  
61Hole Diamond Board  8Move  ≥15  No solution on this board can be shorter than 14 moves. The shortest solution I have found has 15 moves (g6complement). 
"Number of Solutions" is the number of distinct move sequences possible, not counting the order of moves or solutions equivalent by symmetry (rotations or reflections). "Longest Sweep" is the longest sweep possible in any solution of minimum length.
An analytical proof that a solution has minimum length is ideal (if a length is proven minimal analytically, it is listed in bold).
Copyright © 2007 by George I. Bell