Solve triangle solitaire puzzle
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
<lang 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:
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 to 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 8 to 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 10 to 3 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 to 6 1 0 1 0 0 1 1 1 0 1 0 1 1 1 1 11 to 4 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 2 to 7 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 9 to 2 1 0 1 0 0 0 1 1 0 0 0 0 1 1 1 0 to 5 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 6 to 8 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 13 to 11 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 5 to 12 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 11 to 13 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 14 to 12 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 Solved