Solve a Holy Knight's tour
You are encouraged to solve this task according to the task description, using any language you may know.
Night's tours are similar to Hidato. When learning to play chess coaches torture (instruct) their charges by taking a chess board, placing some pennies on some squares and requiring that a Knight's tour is constructed which avoids squares with a penny on. The purpose of this task is to produce a solution to such problems. At least demonstrate you program by solving the following:
- Example 1
0 0 0
0 0 0
0 0 0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0 0 0
0 0 0
0 0 0
Extra credit is available for other interesting examples.
REXX
This REXX program is essentially a modified knight's tour REXX program with support to place pennies on the chessboard.
Also supported is the specification of the size of the chessboard and the placement of the knight (initial position).
<lang rexx>/*REXX pgm solves the holy knight's tour problem for a NxN chessboard.*/
blank=pos('//',space(arg(1),0))\==0 /*see if pennies are to be shown.*/
parse arg ops '/' cent /*obtain the options and pennies.*/
parse var ops N sRank sFile . /*boardsize, starting pos, pennys*/
if N== | N==',' then N=8 /*Boardsize specified? Default. */
if sRank== then sRank=N /*starting rank given? Default. */
if sFile== then sFile=1 /* " 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=' '; end /*f*/; end /*r*/
/*[↑] blank the NxN chessboard.*/
cent=space(translate(cent,,',')) /*allow use of comma (,) for sep.*/ cents=0 /*number of pennies on chessboard*/
do while cent\= /* [↓] possibly place pennies. */
parse var cent cr cf x '/' cent /*extract where to place pennies.*/
if x= then x=1 /*if # not specified, use 1 penny*/
if cr= then iterate /*support the "blanking" option. */
do cf=cf for x /*now, place X pennies on board*/
@.cr.cf='¢' /*mark board position with penny.*/
end /*cf*/ /* [↑] places X pennies on board*/
end /*while cent¬= */ /* [↑] allows of placing X ¢s.*/
/* [↓] traipse through the board*/
do r=1 for N; do f=1 for N; cents=cents+(@.r.f=='¢'); end; end
/* [↑] count number of pennies. */
if cents\==0 then say cents 'pennies placed on chessboard.' target=NN-cents /*use this as the number of moves*/ 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 8 /*legal knight moves. */
Kr.i=word(Kr,i); Kf.i=word(Kf,i)
end /*i*/ /* [↑] fast indexing.*/
!=left(, 9*(n<18)) /*used for indentation of board. */ if @.sRank.sFile==' ' then @.sRank.sFile=1 /*knight's starting pos*/ if @.sRank.sFile\==1 then say 'placing the damn knight.' if @.sRank.sFile\==1 then do sRank=1 for N /*find a starting rank.*/
do sFile=1 for N /* " " " file.*/
if @.sRank.sFile==' ' then do /*got a spot*/
@.sRank.sFile=1
leave sRank
end
end /*sRank*/
end /*sFile*/
if \move(2,sRank,sFile) & ,
\(N==1) then do
say "No knight's tour solution for" NxN'.'
end
else say "A solution for the knight's tour on" NxN':' /*good*/
!: _=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; L=L'║'centre(@.r.f,3) /*preserve squareness.*/
end /*f*/
if blank then L=translate(L,,'¢') /*blank out the pennies ? */
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*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────MOVE subroutine─────────────────────*/ move: procedure expose @. Kr. Kf. N target; parse arg #,rank,file; b=' '
do t=1 for 8; nr=rank+Kr.t; nf=file+Kf.t
if @.nr.nf==b then do; @.nr.nf=# /*Kn move.*/
if #==target then return 1 /*last mv?*/
if move(#+1,nr,nf) then return 1
@.nr.nf=b /*undo the above move. */
end /*try different move. */
end /*t*/
return 0 /*the tour not possible.*/</lang>
output when the following is used for input:
, 3 1 /1,1 3 /1,7 2 /2,1 2 /2,5 /2,8 /3,8 /4,2 /4,4 2 /5,4 2 /5,6 /6,1 /7,1 2 /7,4 /7,7 1 /8,1 2 /8,6 3
26 pennies placed on chessboard.
A solution for the knight's tour on a 8x8 chessboard:
╔═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╗
║ ¢ ║ ¢ ║26 ║35 ║ 4 ║ ¢ ║ ¢ ║ ¢ ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ ¢ ║ ¢ ║ 3 ║ ¢ ║25 ║16 ║ ¢ ║ 6 ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ ¢ ║27 ║36 ║17 ║34 ║ 5 ║24 ║15 ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║37 ║ 2 ║33 ║ ¢ ║ ¢ ║ ¢ ║ 7 ║22 ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║28 ║ ¢ ║18 ║ ¢ ║ ¢ ║23 ║14 ║ 9 ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ 1 ║38 ║29 ║32 ║13 ║ 8 ║21 ║ ¢ ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ ¢ ║ ¢ ║12 ║19 ║ ¢ ║31 ║10 ║ ¢ ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ ¢ ║ ¢ ║ ¢ ║30 ║11 ║20 ║ ¢ ║ ¢ ║
╚═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╝
output when the following is used for input:
, 3 1 /1,1 3 /1,7 2 /2,1 2 /2,5 /2,8 /3,8 /4,2 /4,4 2 /5,4 2 /5,6 /6,1 /7,1 2 /7,4 /7,7 1 /8,1 2 /8,6 3 //
26 pennies placed on chessboard.
A solution for the knight's tour on a 8x8 chessboard:
╔═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╗
║ ║ ║26 ║35 ║ 4 ║ ║ ║ ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ ║ ║ 3 ║ ║25 ║16 ║ ║ 6 ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ ║27 ║36 ║17 ║34 ║ 5 ║24 ║15 ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║37 ║ 2 ║33 ║ ║ ║ ║ 7 ║22 ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║28 ║ ║18 ║ ║ ║23 ║14 ║ 9 ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ 1 ║38 ║29 ║32 ║13 ║ 8 ║21 ║ ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ ║ ║12 ║19 ║ ║31 ║10 ║ ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ ║ ║ ║30 ║11 ║20 ║ ║ ║
╚═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╝
Ruby
This solution uses HLPsolver from here <lang ruby> require 'HLPsolver'
ADJACENT = [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]
boardy = <<EOS , . . 0 0 0 , . . 0 . 0 0 , . 0 0 0 0 0 0 0 . , 0 0 0 . . 0 . 0 , 0 . 0 . . 0 0 0 , 1 0 0 0 0 0 0 , . . 0 0 . 0 , . . . 0 0 0
EOS t0 = Time.now HLPsolver.new(boardy).solve puts " #{Time.now - t0} sec" </lang>
Which produces:
Problem:
0 0 0
0 0 0
0 0 0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0 0 0
0 0 0
0 0 0
Solution:
8 33 14
13 7 32
9 34 31 22 15 6 29
35 12 21 30 16
10 36 23 28 5
1 20 11 24 27 4 17
2 19 25
26 3 18
0.008917049 sec