Knight's tour: Difference between revisions

Content added Content deleted
m (→‎{{header|REXX}}: changed the default starting position (faster by around 25%).)
m (→‎{{header|REXX}}: changed the chessboard grid to more simple "boxing" gylphs.)
Line 3,117: Line 3,117:
<br>The boardsize may be specified as well as the knight's starting position.
<br>The boardsize may be specified as well as the knight's starting position.
<lang rexx>/*REXX program solves the knight's tour problem for a NxN chessboard.*/
<lang rexx>/*REXX program solves the knight's tour problem for a NxN chessboard.*/
parse arg N begRank begFile . /*boardsize, starting position. */
parse arg N sRank sFile . /*boardsize, starting position. */
if N=='' | N==',' then N=8 /*Boardsize specified? Default. */
if N=='' | N==',' then N=8 /*Boardsize specified? Default. */
if begRank=='' then begRank=N /*starting rank given? Default. */
if sRank=='' then sRank=N /*starting rank given? Default. */
if begFile=='' then begFile=1 /* " file " " */
if sFile=='' then sFile=1 /* " file " " */
!=left('', 9*(n<18)) /*used for indentation of board. */
NN=N**2; NxN='a ' N"x"N ' chessboard' /* [↓] r=Rank, f=File.*/
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*/
@.=; do r=1 for N; do f=1 for N; @.r.f=' '; end /*f*/; end /*r*/
/*[↑] zero the NxN chessboard.*/
/*[↑] zero the NxN chessboard.*/
Kr = '2 1 -1 -2 -2 -1 1 2' /*legal "rank" move for a knight.*/
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" " " " " */
Kf = '1 2 2 1 -1 -2 -2 -1' /* " "file" " " " " */
do i=1 for 8 /*legal knight moves*/
do i=1 for words(Kr) /*legal knight moves*/
Kr.i = word(Kr,i); Kf.i = word(Kf,i)
Kr.i = word(Kr,i); Kf.i = word(Kf,i)
end /*i*/ /*for fast indexing.*/
end /*i*/ /*for fast indexing.*/
@.begRank.begFile=1 /*the knight's starting position.*/
@.sRank.sFile=1 /*the knight's starting position.*/
if \move(2,begRank,begFile) & ,
if \move(2,sRank,sFile) & ,
\(N==1) then do
\(N==1) then say "No knight's tour solution for" NxN'.'
say "No knight's tour solution for" NxN'.'
else say "A solution for the knight's tour on" NxN':'
⚫
_=substr(copies("┼───",N),2); say; say ! translate('┌'_"┐", '┬', "┼")
exit /*stick a fork in it, we're done.*/
end
do r=N for N by -1; if r\==N then say ! '├'_"┤"; L=@.
⚫
do f=1 for N; L=L'│'centre(@.r.f,3) /*preserve squareness.*/
say "A solution for the knight's tour on" NxN':'; !=left('', 9*(n<18))
⚫
end /*f*/ /*done with a rank on chessboard.*/
⚫
_=substr(copies("╬═══",N),2); say; say ! translate('╔'_"╗", '╦', "╬")
do r=N for N by -1; if r\==N then say ! '╠'_"╣"; L=@.
say ! L'│' /*show a rank of the chessboard.*/
⚫
do f=1 for N; L=L'║'centre(@.r.f,3) /*preserve squareness.*/
end /*f*/
⚫
say ! L'║' /*show a rank of the chessboard.*/
end /*r*/ /*80 cols can view 19x19 chessbrd*/
end /*r*/ /*80 cols can view 19x19 chessbrd*/
say ! translate('╚'_"╝", '╩', "╬") /*show the last rank of the board*/
say ! translate('└'_"┘", '┴', "┼") /*show the last rank of the board*/
exit /*stick a fork in it, we're done.*/
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────MOVE subroutine─────────────────────*/
/*──────────────────────────────────MOVE subroutine─────────────────────*/
move: procedure expose @. Kr. Kf. N NN; parse arg #,rank,file
move: procedure expose @. Kr. Kf. N NN; parse arg #,rank,file; b=' '
do t=1 for 8; nr=rank+Kr.t; nf=file+Kf.t
do t=1 for 8; nr=rank+Kr.t; nf=file+Kf.t
if @.nr.nf==0 then do; @.nr.nf=# /*Kn move.*/
if @.nr.nf==b then do; @.nr.nf=# /*Kn move.*/
if #==NN then return 1 /*last mv?*/
if #==NN then return 1 /*last mv?*/
if move(#+1,nr,nf) then return 1
if move(#+1,nr,nf) then return 1 /* " " */
@.nr.nf=0 /*undo the above move. */
@.nr.nf=b /*undo the above move. */
end /*try different move. */
end /*try different move. */
end /*t*/
end /*t*/ /* [↑] all moves tried.*/
return 0 /*the tour not possible.*/</lang>
return 0 /*the tour not possible.*/</lang>
'''output'''
'''output'''
Line 3,158: Line 3,156:
A solution for the knight's tour on a 8x8 chessboard:
A solution for the knight's tour on a 8x8 chessboard:


┌───┬───┬───┬───┬───┬───┬───┬───┐
╔═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╗
║52 ║47 ║56 ║45 ║54 ║ 5 ║22 ║13 ║
│ 1 │38 │55 │34 │ 3 │36 │19 │22 │
├───┼───┼───┼───┼───┼───┼───┼───┤
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║57 ║44 ║53 ║ 4 ║23 ║14 ║25 ║ 6 ║
│54 │47 │ 2 │37 │20 │23 │ 4 │17 │
├───┼───┼───┼───┼───┼───┼───┼───┤
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║48 ║51 ║46 ║55 ║26 ║21 ║12 ║15 ║
│39 │56 │33 │46 │35 │18 │21 │10 │
├───┼───┼───┼───┼───┼───┼───┼───┤
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║43 ║58 ║ 3 ║50 ║41 ║24 ║ 7 ║20 ║
│48 │53 │40 │57 │24 │11 │16 │ 5 │
├───┼───┼───┼───┼───┼───┼───┼───┤
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║36 ║49 ║42 ║27 ║62 ║11 ║16 ║29 ║
│59 │32 │45 │52 │41 │26 │ 9 │12 │
├───┼───┼───┼───┼───┼───┼───┼───┤
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║59 ║ 2 ║37 ║40 ║33 ║28 ║19 ║ 8 ║
│44 │49 │58 │25 │62 │15 │ 6 │27 │
├───┼───┼───┼───┼───┼───┼───┼───┤
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║38 ║35 ║32 ║61 ║10 ║63 ║30 ║17 ║
│31 │60 │51 │42 │29 │ 8 │13 │64 │
├───┼───┼───┼───┼───┼───┼───┼───┤
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ 1 ║60 ║39 ║34 ║31 ║18 ║ 9 ║64 ║
│50 │43 │30 │61 │14 │63 │28 │ 7 │
└───┴───┴───┴───┴───┴───┴───┴───┘
╚═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╝
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Knight%27s_tour"