Solve triangle solitaire puzzle

Solve triangle solitaire puzzle is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

An IQ Puzzle is a triangle of 15 golf tee's This is typically seen at Cracker Barrel where one tee is missing and the remaining tees jump each other until one tee is left. The fewer tees left the higher the IQ score. peg #1 is the top centre through to the bottom row which are pegs 11 through to 15.

(Note: need ASCII art version of reference picture http://www.joenord.com/puzzles/peggame/)

Task description

Print a solution to solve the puzzle leaving one peg Not implemented variations Start with empty peg in X and solve with one peg in position Y.

Python

<lang Python >#

1. Draw board triangle in ascii

def DrawBoard(board):

 peg = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
 for n in xrange(1,16):
   peg[n] = '.'
   if(n in board):
     peg[n] = "%X" % n
 print "     %s" % peg[1]
 print "    %s %s" % (peg[2],peg[3])
 print "   %s %s %s" % (peg[4],peg[5],peg[6])
 print "  %s %s %s %s" % (peg[7],peg[8],peg[9],peg[10])
 print " %s %s %s %s %s" % (peg[11],peg[12],peg[13],peg[14],peg[15])

1. remove peg n from board and return board

def RemovePeg(board,n):

 i = board.index(n)
 del(board[i])
 return board

1. Add peg n on board and return board

def AddPeg(board,n):

 board.append(n)
 return board

1. return true if peg N is on board else false is empty position

def IsPeg(board,n):

 return n in board

1. A dictionary of valid jump moves index by jumping peg
2. then a list of moves where move has jumpOver and LandAt positions

JumpMoves = { 1: [ [2,4],[3,6] ], # 1 can jump over 2 to land on 4, or jumper over 3 to land on 6

             2: [ [4,7],[5,9]  ],
             3: [ [5,8],[6,10] ],
             4: [ [2,1],[5,6],[7,11],[8,13] ],
             5: [ [8,12],[9,14] ],
             6: [ [3,1],[5,4],[9,13],[10,15] ],
             7: [ [4,2],[8,9]  ],
             8: [ [5,3],[9,10] ],
             9: [ [5,2],[8,7]  ],
            10: [ [9,8] ],
            11: [ [12,13] ],
            12: [ [8,5],[13,14] ],
            13: [ [8,4],[9,6],[12,11],[14,15] ],
            14: [ [9,5],[13,12]  ],
            15: [ [10,6],[14,13] ]
           }

Solution = []

2. Recursively solve the problem

def Solve(board):

 #DrawBoard(board)
 if(len(board) == 1):
   return board # Solved one peg left
 # try a move for each peg on the board
 for peg in xrange(1,16): # try in numeric order not board order
   if(IsPeg(board,peg)):
     movelist = JumpMoves[peg]
     for move in movelist:
       over = move[0]
       land = move[1]
       if(IsPeg(board,over) and not IsPeg(board,land)):
         saveboard = board[:] # for back tracking
         RemovePeg(board,peg)
         RemovePeg(board,over)
         AddPeg(board,land) # board order changes!

         Solution.append([peg,over,land])

         board = Solve(board)
         if(len(board) == 1):
           return board
       ## undo move and back track when stuck!
         board = saveboard[:] # back track
         del(Solution[-1]) # remove last move
 return board

2. Remove one peg and start solving

def InitSolve(empty):

 board = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
 board= RemovePeg(board,empty_start)
 Solve(board)

empty_start = 1 InitSolve(empty_start)

board = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] board= RemovePeg(board,empty_start) for move in Solution:

 peg = move[0]
 over = move[1]
 land = move[2]
 RemovePeg(board,peg)
 RemovePeg(board,over)
 AddPeg(board,land) # board order changes!
 DrawBoard(board)
 print "Peg %X jumped over %X to land on %X\n" % (peg,over,land)

</lang>

Output:

     1
    . 3
   . 5 6
  7 8 9 A
 B C D E F
Peg 4 jumped over 2 to land on 1

     1
    . 3
   4 . .
  7 8 9 A
 B C D E F
Peg 6 jumped over 5 to land on 4

     .
    . .
   4 . 6
  7 8 9 A
 B C D E F
Peg 1 jumped over 3 to land on 6

     .
    2 .
   . . 6
  . 8 9 A
 B C D E F
Peg 7 jumped over 4 to land on 2

     .
    2 .
   . 5 6
  . . 9 A
 B . D E F
Peg C jumped over 8 to land on 5

     .
    2 .
   . 5 6
  . . 9 A
 B C . . F
Peg E jumped over D to land on C

     .
    2 .
   . 5 .
  . . . A
 B C D . F
Peg 6 jumped over 9 to land on D

     .
    . .
   . . .
  . . 9 A
 B C D . F
Peg 2 jumped over 5 to land on 9

     .
    . .
   . . .
  . . 9 A
 B . . E F
Peg C jumped over D to land on E

     .
    . .
   . . 6
  . . 9 .
 B . . E .
Peg F jumped over A to land on 6

     .
    . .
   . . .
  . . . .
 B . D E .
Peg 6 jumped over 9 to land on D

     .
    . .
   . . .
  . . . .
 B C . . .
Peg E jumped over D to land on C

     .
    . .
   . . .
  . . . .
 . . D . .
Peg B jumped over C to land on D