Solve triangle solitaire puzzle: Difference between revisions
Content added Content deleted
m (insert j solution) |
m (→{{header|J}}) |
||
Line 173:
=={{header|J}}==
<lang J>
NB. This is a direct translation of the python program,
NB. except for the display which by move is horizontal.
PEGS =: >:i.15
move =: 4 : 0 NB. move should have been factored in the 2014-NOV-29 python version
board =. x
'peg over land' =. y
board =. board RemovePeg peg
board =. board RemovePeg over
board =. board AddPeg land
)
NB.# Draw board triangle in ascii
NB.#
NB.def DrawBoard(board):
NB. peg = [0,]*16
NB. for n in xrange(1,16):
NB. peg[n] = '.'
NB. if n in board:
NB. peg[n] = "%X" % n
NB. print " %s" % peg[1]
NB. print " %s %s" % (peg[2],peg[3])
NB. print " %s %s %s" % (peg[4],peg[5],peg[6])
NB. print " %s %s %s %s" % (peg[7],peg[8],peg[9],peg[10])
NB. print " %s %s %s %s %s" % (peg[11],peg[12],peg[13],peg[14],peg[15])
HEXCHARS =: Num_j_ , Alpha_j_
DrawBoard =: 3 : 0
NB. observe 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 -: 2#.inv 26896
board =. y
< (-i._5) (|."0 1) 1j1 (#"1) (2#.inv 26896)[;.1 }. (board { HEXCHARS) board } 16 # '.'
)
NB.# remove peg n from board
NB.def RemovePeg(board,n):
NB. board.remove(n)
NB. return board
RemovePeg =: i. ({. , (}.~ >:)~) [
NB.# Add peg n on board
NB.def AddPeg(board,n):
NB. board.append(n)
NB. return board
AddPeg =: ,
NB.# return true if peg N is on board else false is empty position
NB.def IsPeg(board,n):
NB. return n in board
IsPeg =: e.~
NB.# A dictionary of valid jump moves index by jumping peg
NB.# then a list of moves where move has jumpOver and LandAt positions
NB.JumpMoves = { 1: [ (2,4),(3,6) ], # 1 can jump over 2 to land on 4, or jumper over 3 to land on 6
NB. 2: [ (4,7),(5,9) ],
NB. 3: [ (5,8),(6,10) ],
NB. ...
NB. 14: [ (9,5),(13,12) ],
NB. 15: [ (10,6),(14,13) ]
NB. }
JumpMoves =: a:,(<@:([\~ _2:)@:".;._2) 0 :0 NB. 1 can jump over 2 to land on 4, or jump over 3 to land on 6
(2,4),(3,6)
(4,7),(5,9)
(5,8),(6,10)
(2,1),(5,6),(7,11),(8,13)
(8,12),(9,14)
(3,1),(5,4),(9,13),(10,15)
(4,2),(8,9)
(5,3),(9,10)
(5,2),(8,7)
(9,8)
(12,13)
(8,5),(13,14)
(8,4),(9,6),(12,11),(14,15)
(9,5),(13,12)
(10,6),(14,13)
)
NB.Solution = []
NB.#
NB.# Recursively solve the problem
NB.#
NB.def Solve(board):
NB. #DrawBoard(board)
NB. if len(board) == 1:
NB. return board # Solved one peg left
NB. # try a move for each peg on the board
NB. for peg in xrange(1,16): # try in numeric order not board order
NB. if IsPeg(board,peg):
NB. movelist = JumpMoves[peg]
NB. for over,land in movelist:
NB. if IsPeg(board,over) and not IsPeg(board,land):
NB. saveboard = board[:] # for back tracking
NB. board = RemovePeg(board,peg)
NB. board = RemovePeg(board,over)
NB. board = AddPeg(board,land) # board order changes!
NB. Solution.append((peg,over,land))
NB. board = Solve(board)
NB. if len(board) == 1:
NB. return board
NB. ## undo move and back track when stuck!
NB. board = saveboard[:] # back track
NB. del Solution[-1] # remove last move
NB. return board
Solution =: 0 3 $ 0
Solve =: 3 : 0
board =. y
if. 1 = # board do. return. end.
for_peg. PEGS do.
if. board IsPeg peg do.
movelist =: peg {:: JumpMoves
for_OL. movelist do.
'over land' =. OL
if. (board IsPeg over) (*. -.) (board IsPeg land) do.
saveboard =. board NB. for back tracking
board =. board move peg,over,land
Solution =: Solution , peg, over, land
board =. Solve board
if. 1 = # board do. return. end.
board =. saveboard
Solution =: }: Solution
end.
end.
end.
end.
board
)
NB.#
NB.# Remove one peg and start solving
NB.#
NB.def InitSolve(empty):
NB. board = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
NB. RemovePeg(board,empty_start)
NB. Solve(board)
InitSolve =: [: Solve PEGS RemovePeg ]
NB.#
NB.empty_start = 1
NB.InitSolve(empty_start)
InitSolve empty_start =: 1
NB.board = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
NB.RemovePeg(board,empty_start)
NB.for peg,over,land in Solution:
NB. RemovePeg(board,peg)
NB. RemovePeg(board,over)
NB. AddPeg(board,land) # board order changes!
NB. DrawBoard(board)
NB. print "Peg %X jumped over %X to land on %X\n" % (peg,over,land)
(3 : 0) PEGS RemovePeg empty_start
board =. y
horizontal =. DrawBoard board
for_POL. Solution do.
'peg over land' =. POL
board =. board move POL
horizontal =. horizontal , DrawBoard board
smoutput 'Peg ',(":peg),' jumped over ',(":over),' to land on ',(":land)
end.
smoutput horizontal
NB. Solution NB. return Solution however Solution is global.
)
</lang>
<pre>
</pre>
|