Pegs jumping

Matt Parker’s newest Maths Puzzle asks you to provide the shortest solution to a triangular peg jumping puzzle. Start with ten pegs in ten holes arranged in a triangle:

Remove one peg. Now start jumping pegs, checkers style, but in any of six directions. For instance if peg 1 is removed then you can jump peg 4 over peg 2 into position 1, or peg 6 over peg 3 into position 1. The jumped peg is removed. That’s a move, but if you can jump two or more pegs in succession with the same peg (removing them all) that counts as a single move too. Non jumping moves are not allowed. Keep going until you’re left with only one peg, or there are no legal jumps.

There are ten pegs but really only three pegs to consider removing: A corner peg like 1, an edge peg like 2, or the center peg, 5. In each case what’s the best strategy for clearing the board? Can you clear the board, and in how few moves? For bonus points, can you find ways of winning with the last peg left in a given position?

This is a small and simple enough game that you can work out the game graph by hand — if you’re careful. I kept overlooking moves, getting confused, running out of space on my paper, so I ended up writing a Python script to do it. Which I’m not going to share here, because I wrote it mainly in the middle of the night and yeesh. But in a nutshell it works recursively, finding all possible jumps from a starting position and then finding all possible jumps from those positions, et cetera. Consecutive jumps with the same peg are consolidated into single moves and the number of moves are tallied.

Results are shown below. Ready for some old school ASCII graphics?

The output shows first, for the case where you start with an edge peg (in position 2) missing, the 62 positions you can reach. (Some positions are the same under reflection and rotation, but for the purposes of finding solutions, it’s easier to regard these separately.) For each position there is shown an index (0 to 61), an ASCII representation of the position, and a list of the new positions you can reach in a single jump from there. Or if there are no legal jumps, it says “wins” if there is only one peg left, “loses” otherwise. #11 is the only winning position, with the last peg in position 3. So, no, you can’t find optimal ways of finishing with the peg in position 9, for instance, because there are no ways.

Below that are the solutions, with jumps combined into single multi-jump moves where possible. On each line is the series of moves (expressed as two or more numbers: the position of the jumping peg, and the position(s) it jumps into), then the series of positions (or rather their index numbers), and then the number of moves. There are 14 solutions, some of which involve the same positions at the end of each move, but in those cases there’s a cyclic series of three jumps ending in the original place; it can go clockwise or counterclockwise, and those are counted as separate solutions. The shortest solutions are five moves, including one such cyclic triple jump plus another double jump. Of the two possible starting moves (7-2 and 9-2), only the former leads to a win, but from there any of the three possible second moves can be used. All solutions end in position #11, of course.

Below that is the same output for the case where you start with a corner peg missing. There are 42 positions, none winning (Douglas Adams would have liked that), no solutions.

Below that is the same for the case where you start with the center peg missing. There is 1 position. You can’t win. You can’t even move. Sounds familiar.

Starting with
   o
  - o
 o o o
o o o o

# 0            # 1            # 2            # 3            # 4            
       o              o              -              o              o       
      - o            o o            - o            - -            - -      
     o o o          - o o          o o o          o o -          - - o     
    o o o o        - o o o        - o o o        - o o o        - o o o    
->  1 59       ->  2 39 48    ->  3 25 31    ->  4 13 18 22 ->  5  8       
---------------------------------------------------------------------------
# 5            # 6            # 7            # 8            # 9            
       o              o              -              o              -       
      - -            - o            - -            - o            - -      
     - - o          - - -          - - o          - - -          - - o     
    o - - o        o - - -        o - - -        - o o -        - o o -    
->  6          ->  7          loses          ->  9 12  6    -> 10  7       
---------------------------------------------------------------------------
#10            #11            #12            #13            #14            
       -              -              o              o              -       
      - -            - o            - o            - o            - -      
     - - o          - - -          - - -          o - -          o - o     
    - - - o        - - - -        - - - o        - - o o        - - o o    
-> 11          wins           -> 10          -> 14 17       -> 15 16       
---------------------------------------------------------------------------
#15            #16            #17            #18            #19            
       -              -              o              o              o       
      - o            - -            - o            o -            - -      
     o - -          o - o          o - -          o - -          - - -     
    - - o -        - o - -        - o - -        - o - o        o o - o    
loses          loses          -> 16          -> 19          -> 20          
---------------------------------------------------------------------------
#20            #21            #22            #23            #24            
       o              o              o              o              -       
      - -            - -            - -            o -            - -      
     - - -          - - -          o o -          - o -          o o -     
    - - o o        - o - -        o - - o        - - - o        - - - o    
-> 21          loses          ->  5 23       -> 24 20       -> 10          
---------------------------------------------------------------------------
#25            #26            #27            #28            #29            
       -              -              -              -              -       
      o o            - o            - o            - o            - -      
     o - o          - - o          - - o          - - o          - - -     
    - o - o        o o - o        - - o o        - o - -        - o - o    
-> 26 30 18    -> 19 27       -> 20 28       -> 29 21       loses          
---------------------------------------------------------------------------
#30            #31            #32            #33            #34            
       o              -              -              -              -       
      - o            - o            - -            o -            o o      
     - - o          o o o          o - o          - - o          - - -     
    - o - o        o - - o        o o - o        - o - o        - o - -    
loses          -> 32 22 36    -> 33 14 35    -> 34          loses          
---------------------------------------------------------------------------
#35            #36            #37            #38            #39            
       -              -              -              -              o       
      - o            o o            o o            - o            o o      
     o - -          - o o          o - -          - - -          o - -     
    o o - -        - - - o        - - - o        o - - o        - o o o    
-> 34 15       -> 27 33 23 37 -> 38 12       loses          -> 40 46 47    
---------------------------------------------------------------------------
#40            #41            #42            #43            #44            
       -              -              -              -              -       
      o -            - -            - o            o -            o o      
     o - o          - - o          - - -          o - o          o - -     
    - o o o        o o o o        o o o -        o - - o        o - - -    
-> 41  4 43 45 -> 42          -> 38          ->  5 44       ->  6          
---------------------------------------------------------------------------
#45            #46            #47            #48            #49            
       -              o              o              o              o       
      o o            - o            o o            o o            - o      
     o - -          - - -          o - -          - o o          - - o     
    - o o -        o o o o        o - - o        o - - o        o - o o    
-> 42  8 37 44 -> 41          -> 43          -> 31 49 52 47 -> 50          
---------------------------------------------------------------------------
#50            #51            #52            #53            #54            
       o              o              o              o              o       
      - o            - o            o -            o -            o o      
     - - o          - - o          - - o          - - o          - - -     
    o o - -        - - o -        o o - o        - - o o        - - o -    
-> 19 51       -> 20          -> 32 53 57    -> 14 54 56    -> 15 55       
---------------------------------------------------------------------------
#55            #56            #57            #58            #59            
       -              o              o              -              o       
      o -            o -            o o            o -            o o      
     - - o          - - o          - - -          - - o          o - o     
    - - o -        - o - -        o o - -        o o - -        o o - o    
loses          -> 16          -> 35 58 54    -> 55          -> 60          
---------------------------------------------------------------------------
#60            #61            
       o              o       
      o o            o o      
     o - o          o - o     
    - - o o        - o - -    
-> 49 61       -> 50 18       
---------------------------------------------------------------------------
Solutions:
  7-2  1-4  6-1  4-6  10-3  1-6  8-10-3  |   0 1 2 3 4 8 9 11  |  7 moves
  7-2  1-4  6-1  4-6  10-3  8-10  1-6  10-3  |   0 1 2 3 4 8 12 10 11  |  8 moves
  7-2  1-4  6-1  9-7-2  1-4-6  10-3  |   0 1 2 3 23 10 11  |  6 moves
  7-2  1-4  9-7  6-1  7-2  1-4-6  10-3  |   0 1 2 31 22 23 10 11  |  7 moves
  7-2  1-4  9-7-2  6-1-4-6  10-3  |   0 1 2 36 10 11  |  5 moves
  7-2  1-4  9-7-2  6-4-1-6  10-3  |   0 1 2 36 10 11  |  5 moves
  7-2  6-4  1-6  4-1  10-3  1-6  8-10-3  |   0 1 39 40 4 8 9 11  |  7 moves
  7-2  6-4  1-6  4-1  10-3  8-10  1-6  10-3  |   0 1 39 40 4 8 12 10 11  |  8 moves
  7-2  6-4  1-6  10-3  4-1-6  8-10-3  |   0 1 39 40 45 9 11  |  6 moves
  7-2  6-4  1-6  10-3  4-1  8-10  1-6  10-3  |   0 1 39 40 45 8 12 10 11  |  8 moves
  7-2  6-4  1-6  10-3  8-10  4-1-6  10-3  |   0 1 39 40 45 37 10 11  |  7 moves
  7-2  9-7  1-4  6-1  7-2  1-4-6  10-3  |   0 1 48 31 22 23 10 11  |  7 moves
  7-2  9-7  1-4  7-2  6-1-4-6  10-3  |   0 1 48 31 36 10 11  |  6 moves
  7-2  9-7  1-4  7-2  6-4-1-6  10-3  |   0 1 48 31 36 10 11  |  6 moves

Starting with
   -
  o o
 o o o
o o o o

# 0            # 1            # 2            # 3            # 4            
       -              o              o              -              -       
      o o            - o            - o            - -            o -      
     o o o          - o o          o - -          o - o          - - o     
    o o o o        o o o o        o o o o        o o o o        - o o o    
->  1 26       ->  2 14       ->  3 11       ->  4  9       ->  5  7       
---------------------------------------------------------------------------
# 5            # 6            # 7            # 8            # 9            
       -              -              -              -              -       
      o -            o o            o o            o o            - o      
     - - o          - - -          - - -          - - -          o - -     
    o - - o        o - - -        - o o -        - - - o        o o o -    
->  6          loses          ->  8  6       loses          ->  7 10       
---------------------------------------------------------------------------
#10            #11            #12            #13            #14            
       -              o              -              o              o       
      - o            o o            - o            o o            o o      
     o - -          - - -          o - -          - - -          - - o     
    o - - o        - o o o        - o o o        o - - o        o o - o    
->  8          -> 12  4 13    -> 10          -> 10  5       -> 15 24       
---------------------------------------------------------------------------
#15            #16            #17            #18            #19            
       -              o              o              -              o       
      - o            - -            o -            - -            - -      
     o - o          o - -          - - -          o - -          o - -     
    o o - o        o o - o        - o - o        - o - o        - - o o    
-> 16 21 22    -> 17 19       -> 18          loses          -> 20          
---------------------------------------------------------------------------
#20            #21            #22            #23            #24            
       o              -              -              -              o       
      - -            o o            - o            - o            o o      
     o - -          - - o          o - o          o - o          - - o     
    - o - -        - o - o        - - o o        - o - -        - - o o    
loses          -> 17          -> 19 23       -> 18 20       -> 22 25       
---------------------------------------------------------------------------
#25            #26            #27            #28            #29            
       o              o              o              o              -       
      o o            o -            o -            o o            o -      
     - - o          o o -          - - o          - - -          - - o     
    - o - -        o o o o        o o o o        o o o -        o o o -    
-> 23 17       -> 27 30       ->  3 28       ->  9 29 13    ->  5          
---------------------------------------------------------------------------
#30            #31            #32            #33            #34            
       o              -              o              o              -       
      o o            o -            - -            - o            - -      
     o - -          o - o          - - o          - - -          - - o     
    o - o o        o - o o        o - o o        o - o -        o - o -    
-> 31 40       -> 32 37 38    -> 33 35       -> 34          loses          
---------------------------------------------------------------------------
#35            #36            #37            #38            #39            
       o              o              -              -              -       
      - -            - -            o o            o -            o -      
     - - o          - - o          o - -          o - o          o - o     
    o o - -        - - o -        o - o -        o o - -        - - o -    
-> 36          loses          -> 33          -> 35 39       -> 34 36       
---------------------------------------------------------------------------
#40            #41            
       o              o       
      o o            o o      
     o - -          o - -     
    o o - -        - - o -    
-> 38 41       -> 39 33       
---------------------------------------------------------------------------
No solutions

Starting with
   o
  o o
 o - o
o o o o

# 0            
       o       
      o o      
     o - o     
    o o o o    
loses          
---------------------------------------------------------------------------
No solutions

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s