Solve triangle solitaire puzzle: Difference between revisions

Content added Content deleted

Inline

Revision as of 12:52, 19 October 2014

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>#

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])

remove peg n from board

def RemovePeg(board,n):

 board.remove(n)

Add peg n on board

def AddPeg(board,n):

 board.append(n)

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

def IsPeg(board,n):

 return n in board

A dictionary of valid jump moves index by jumping peg
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 = []

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 over,land in movelist:
       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

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]
 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] RemovePeg(board,empty_start) for peg,over,land in Solution:

 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

Ruby

Solitaire Like Puzzle Solver

// // Nigel Galloway: October 18th., 2014 N = [0,1,1,1,1,1,1,1,1,1,1,1,1,1,1] G = [[0,1,3],[0,2,5],[1,3,6],[1,4,8],[2,4,7],[2,5,9],[3,4,5],[3,6,10],[3,7,12],[4,7,11],[4,8,13],[5,8,12],[5,9,14],[6,7,8],[7,8,9],[10,11,12],[11,12,13],[12,13,14]]

def b2s n

 "    #{n[0]}\n   #{n[1]} #{n[2]}\n  #{n[3]} #{n[4]} #{n[5]}\n #{n[6]} #{n[7]} #{n[8]} #{n[9]}\n#{n[10]} #{n[11]} #{n[12]} #{n[13]} #{n[14]}\n\n"

end def solve n,i,g

 return "Solved" if i == 14
 return false unless n[g[1]]==1
 if n[g[0]] == 0
   return false unless n[g[2]]==1
   s =  "#{g[2]} to #{g[0]}\n"
 else
   return false unless n[g[2]]==0
   s = "#{g[0]} to #{g[2]}\n" 
 end
 a = n.clone; g.each{|n| a[n] = 1 - a[n]}
 l=false; G.each{|g| l=solve(a,i+1,g); break if l}
 return l ? s + b2s(a) + l : l

end puts b2s N l=false; G.each{|g| l=solve(N,1,g); break if l} puts l ? l : "No solution found" </lang>

Output: