Essays/Knight's Tour
A knight's tour is a traversal by a knight of a chessboard, visiting each square exactly once.
Depth First Search
ktour uses a depth first search strategy, stopping on finding the first solution (or on failing to find a solution).
NB. knight moves for each square of a (y,y) board
kmoves=: 3 : 0
t=. (>,{;~i.y) +"1/ _2]\2 1 2 _1 1 2 1 _2 _1 2 _1 _2 _2 1 _2 _1
(*./"1 t e. i.y) <@#"1 y#.t
)
ktour=: 3 : 0
if. 1>:y do. i.,~y return. end.
m=. kmoves y
p=. *:y
stack=. ,&.>|.y (<:/~@] #&, * +/ ]) i.>.-:y
while. #stack do.
s=. >{:stack
if. a: e. (((i.p)-.s){m)-.&.><s do.
if. (#s)=p-1 do. (,~y)$/:s,(i.p)-.s return. end.
stack=. }:stack continue.
end.
stack=. (}:stack),(<s),&.>s-.~({:s){::m
end.
)
For example:
ktour 8 0 11 8 5 2 13 16 19 9 6 1 12 17 20 3 14 30 27 10 7 4 15 18 21 63 24 31 28 35 22 47 44 32 29 26 23 48 45 36 57 25 62 51 34 39 56 43 46 52 33 60 49 54 41 58 37 61 50 53 40 59 38 55 42
s in ktour is a partial tour. Suppose that relative to s there is an unvisited square having no unvisited neighbor. Then that square must be the final destination and must be one knight move from the last element of s . Otherwise, s can not be the prefix of a tour. The lines
if. a: e. (((i.p)-.s){m)-.&.><s do.
if. (#s)=p-1 do. (,~y)$/:s,(i.p)-.s return. end.
stack=. }:stack continue.
end.
implements this heuristic. ktour 8 executes 302,701 iterations with these lines and 17,739,768 iterations without.
The stack in ktour is initialized to be the squares of the upper northwest octant. By reflectional and transposal symmetry an octant covers all possible starting positions of a tour.
y=: 8 ] i=: y (<:/~@] #&, * +/ ]) i.>.-:y 0 1 2 3 9 10 11 18 19 27 ] t=: (i.y,y) e. i 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (+.|:) (+.|.) (+.|."1) t 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Warnsdorff's Algorithm
Warnsdorff's heuristic algorithm was invented by H.C. Warnsdorff in 1823. The heuristic is to choose a successor having the fewest further moves.
ktourw=: 3 : 0
M=. >kmoves y
p=. k=. 0
b=. 1 $~ *:y
for. i.<:*:y do.
b=. 0 k}b
p=. p,k=. ((i.<./) +/"1 b{~j{M){j=. ({&b # ]) k{M
end.
assert. ~:p
(,~y)$/:p
)
For example:
ktourw 8 0 25 14 23 28 49 12 31 15 22 27 50 13 30 63 48 26 1 24 29 62 59 32 11 21 16 51 58 43 56 47 60 2 41 20 55 52 61 10 33 17 38 53 42 57 44 7 46 40 3 36 19 54 5 34 9 37 18 39 4 35 8 45 6
ktourw is very efficient with ktourw 80 running in about 0.1 seconds.
Collected Definitions
NB. knight moves for each square of a (y,y) board
kmoves=: 3 : 0
t=. (>,{;~i.y) +"1/ _2]\2 1 2 _1 1 2 1 _2 _1 2 _1 _2 _2 1 _2 _1
(*./"1 t e. i.y) <@#"1 y#.t
)
ktour=: 3 : 0
if. 1>:y do. i.,~y return. end.
m=. kmoves y
p=. *:y
stack=. ,&.>|.y (<:/~@] #&, * +/ ]) i.>.-:y
while. #stack do.
s=. >{:stack
if. a: e. (((i.p)-.s){m)-.&.><s do.
if. (#s)=p-1 do. (,~y)$/:s,(i.p)-.s return. end.
stack=. }:stack continue.
end.
stack=. (}:stack),(<s),&.>s-.~({:s){::m
end.
)
NB. Warnsdorff's algorithm
ktourw=: 3 : 0
M=. >kmoves y
p=. k=. 0
b=. 1 $~ *:y
for. i.<:*:y do.
b=. 0 k}b
p=. p,k=. ((i.<./) +/"1 b{~j{M){j=. ({&b # ]) k{M
end.
assert. ~:p
(,~y)$/:p
)
From http://xkcd.com/761/
See also
Contributed by Roger Hui.