Anonymous user
Knight's tour: Difference between revisions
→{{header|REXX}}: added the REXX language. -- ~~~~
(→{{header|REXX}}: added the REXX language. -- ~~~~) |
|||
Line 2,688:
P.S. There is a slight deviation to a strict interpretation of Warnsdorffs algorithm in that as a conveniance, tuples of the length of the night moves followed by the position are minimized so knights moves with the same length will try and break the ties based on their minimum x,y position. In practice, it seems to give comparable results to the original algorithm.
=={{header|REXX}}==
This REXX version is modeled after XPL0.
<lang rexx>/*REXX pgm to solve the knight's tour problem for a NxN chessboard. */
@.= /*define the outside of the board*/
parse arg N .; if N=='' | N==',' then N=8 /*user can specify board size.*/
NN=N**2; NxN='a ' N"x"N ' chessboard' /* [↓] R=rank, F=file. */
do r=1 for N; do f=1 for N; @.r.f=0; end /*f*/; end /*r*/
/*[↑] zero out the NxN chessboard*/
Kr= '2 1 -1 -2 -2 -1 1 2' /*legal "rank" move for a knight.*/
Kf= '1 2 2 1 -1 -2 -2 -1' /* " "file" " " " " */
do i=1 for words(Kr) /*legal moves*/
Kr.i = word(Kr,i); Kf.i = word(Kf,i)
end /*i*/
@.1.1=1 /*the knight's starting position.*/
if N==1 | move(2,1,1) then call show
else say "There's no solution for" NxN'.'
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────MOVE subroutine─────────────────────*/
move: procedure expose @. Kr. Kf. N NN; parse arg ?,r,f
do t=1 for N; nr=r+Kr.t; nf=f+Kf.t
if @.nr.nf==0 then do; @.nr.nf=?
if ?==NN then return 1
if move(?+1,nr,nf) then return 1
@.nr.nf=0
end
end /*t*/
return 0
/*──────────────────────────────────SHOW subroutine─────────────────────*/
show: say "A solution for the knight's tour on" NxN':';!=left('',9*(n<18))
_=substr(copies("┼───",N),2); say; say ! translate('┌'_"┐", '┬', "┼")
do r=N for N by -1; if r\==N then say ! '├'_"┤"; L=
do f=1 for n /*handle the ranks and files. */
L=L'│'center(@.r.f,3) /*trying to preserve squareness. */
end /*f*/
say ! L'│' /*show a rank of the chessboard. */
end /*r*/ /*80 cols can view 19x19 chessbrd*/
say ! translate('└'_"┘", '┴', "┼") /*show the last rank of the board*/
return</lang>
'''output'''
<pre style="overflow:scroll">
A solution for the knight's tour on a 8x8 chessboard:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │60 │39 │34 │31 │18 │ 9 │64 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│38 │35 │32 │61 │10 │63 │30 │17 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│59 │ 2 │37 │40 │33 │28 │19 │ 8 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│36 │49 │42 │27 │62 │11 │16 │29 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│43 │58 │ 3 │50 │41 │24 │ 7 │20 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│48 │51 │46 │55 │26 │21 │12 │15 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│57 │44 │53 │ 4 │23 │14 │25 │ 6 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│52 │47 │56 │45 │54 │ 5 │22 │13 │
└───┴───┴───┴───┴───┴───┴───┴───┘
</pre>
=={{header|Ruby}}==
| |||