## Ken's POTW

Peg Solitaire
The peg-solitaire game of Hi-Q (in the form of a cross) is whimsically dissected and solved at Cut-The-Knot's Peg Solitaire Page. That game inspired me to dig up some others:
1. This game starts with 15 pegs in the form of an equilateral triangle with a base of five pegs. Each move consists of jumping one peg over an existing peg into an empty position. (Jumps are parallel to any of the three sides of the triangle.) The jumped peg is then removed from the board. The goal of the game is to be left with only one peg, preferably left in the original empty hole.
• What is the largest number of pegs that can be left on the board with no moves left (no possible jumps)? You can choose the starting position by removing any peg.
• How many different starting positions exist? Try to solve the original game for all of them.

2. In a 5x5 grid of squares, the center nine squares each have one peg, numbered 1 (in the second row, second column) through 8 clockwise around the center square numbered 9. Each number represents a piece that can jump over any other piece, either vertically, horizontally or diagonally into an empty square beyond. Each piece is removed when it is jumped.
• How can all the pegs be removed, except the 9, which ends up in its original position in the center? What is the smallest number of pegs you need to touch?
Disregarding the end position:
• What is the smallest number of pegs you need to touch?
• What is the smallest number of times you need to change jumping pegs?
• Can the problem be solved without diagonal jumps? If not, what is the smallest number of diagonal jumps needed?

Source: 1. rec.puzzles. 2. Sun-Tsu Suan Ching, c. 400, in The Penguin Book of Curious and Interesting Puzzles, David Wells, 1992, #69

Solutions were received from Phillipe Fondanaiche and Kirk Bresniker.
1.  For the first problem, I find Kirk's graphical solutions easiest to understand. Label the triangle as shown. There are then four different starting positions: 1, 2, 4, and 5. ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ```
 Kirk's answer to largest number of remaining pegs: Start with hole 5 empty. ``` * * * * . * * * * * * * * * * 5 empty ``` ``` * * * * * * * . * * * . * * * 12 - 5 ``` ``` * * . * . * * * * * * . * * * 3 - 8 ``` ``` * * . * * * * * . * * . * . * 14 - 5 ``` ``` * * * * . * * . . * * . * . * 8 - 3 ```
Kirk also found the possible end positions for each starting position:
```1  1 10 13 7
2       2 6 11 14
4       3 4 9 12 15
5       13```
Notice that starting in position 5 means you can ONLY end in position 13. The other starting positions allow an ending in the starting hole. Solutions I've had (A-F = 10-15):
1:4-1,D-4,7-2,B-D,E-C,6-D,C-E,F-D,1-6,A-3,2-9,D-6,6-1
2:7-2,D-4,B-D,E-C,6-D,C-E,F-D,1-6,A-3,3-8,2-7,D-4,7-2
4:1-4,7-2,6-1,1-4,D-6,A-3,F-D,C-E,4-D,E-C,B-D,3-8,D-4
5:C-5,E-C,6-D,F-6,2-9,3-A,A-8,7-2,1-4,C-E,4-D,E-C,B-D.

Kirk's Solutions:
 Start hole 1 ``` . * * * * * * * * * * * * * * ``` ``` * . * . * * * * * * * * * * * ``` ``` * . * * . . * * * * * * * * * ``` ``` . . . * . * * * * * * * * * * ``` ``` . * . . . * . * * * * * * * * ``` ``` . * * . . . . * * . * * * * * ``` ``` . * * . * . . . * . * . * * * ``` ``` . * * . * . . . * . * * . . * ``` ``` . * * . * . . . * . . . * . * ``` ``` . * * . * * . . . . . . . . * ``` ``` . * . . * . . . . * . . . . * ``` ``` . * . . * * . . . . . . . . . ``` ``` . * . * . . . . . . . . . . . ``` ``` * . . . . . . . . . . . . . . ```
 Start hole 2 ``` * . * * * * * * * * * * * * * ``` ``` * * * . * * . * * * * * * * * ``` ``` * * * * . . . * * * * * * * * ``` ``` . * . * . * . * * * * * * * * ``` ``` . . . . . * * * * * * * * * * ``` ``` . . * . . . * * * . * * * * * ``` ``` . . * . * . * . * . * . * * * ``` ``` . . * . * . * . * . * * . . * ``` ``` . . * . * . * . * . . . * . * ``` ``` . . * . * * * . . . . . . . * ``` ``` . . . . * . * . . * . . . . * ``` ``` . . . . * * * . . . . . . . . ``` ``` . . . * . . * . . . . . . . . ``` ``` . * . . . . . . . . . . . . . ```
 Start hole 4 ``` * * * . * * * * * * * * * * * ``` ``` . . * * * * * * * * * * * * * ``` ``` * . . * * . * * * * * * * * * ``` ``` * . . . . * * * * * * * * * * ``` ``` * . * . . . * * * . * * * * * ``` ``` . . . . . * * * * . * * * * * ``` ``` . . . * . * * . * . * * . * * ``` ``` . * . . . * . . * . * * . * * ``` ``` . * . . . * . . * . * * * . . ``` ``` . * . . . * . . * . * . . * . ``` ``` . * . . * * . . . . * . . . . ``` ``` . * . * . . . . . . * . . . . ``` ``` . . . . . . * . . . * . . . . ``` ``` . . . * . . . . . . . . . . . ```
 Start hole 5 ``` * * * * . * * * * * * * * * * ``` ``` * * * * * * * . * * * . * * * ``` ``` * * * * * * * * . . * . * * * ``` ``` * . * * . * * * * . * . * * * ``` ``` * . . * . . * * * * * . * * * ``` ``` * * . . . . . * * * * . * * * ``` ``` . . . * . . . * * * * . * * * ``` ``` . . . * . . . * * * * * . . * ``` ``` . . . . . . . . * * * * * . * ``` ``` . . . . . . . . * * * . . * * ``` ``` . . . . . * . . * . * . . * . ``` ``` . . . . . . . . . . * . * * . ``` ``` . . . . . . . . . . * * . . . ``` ``` . . . . . . . . . . . . * . . ```

2. For the second problem, Phillipe's solution is quite complete:
```We consider the traditional notations of a chess board:

5   *    *    *    *    *
4   *    *    *    *    *
3   *    *    *    *    *
2   *    *    *    *    *
1   *    *    *    *    *
a    b    c    d   e

question 1
The successful sequence in order to put the peg 9 in the position c3,is the
following:
c3-c5, b3-d1, c5-a3-c1-e3, d4-d2, d1-d3, e3-c3
```
[This can be done with fewer peg changes - KD: c3-c5-a3-c1-e3, d4-d2, b3-d1-d3, e3-c3]
```questions 2 and 3
2 pegs only can be touched, for example b3 and c3 in the following sequence:
b3-d1 on one hand and c3-c5-a3-c1-e1-c3-e3-c5 on the other hand

question 4
2 diagonal jumps (D) are at least necessary as described hereafter:
b3-b5, d4-b4, b5-b3, d3-d1, c3-a3, a3-c1 (D),d1-b1,b1-d3 (D)
```

Mail to Ken