26. Knight’s Tour


A knight’s tour is a traversal by a knight of a chessboard,
visiting each square exactly once.
The tour is here computed by depthfirst search
augmented by a heuristic invented by H.C. von Warnsdorf in 1823.
At each step, the heuristic is to choose a successor
having the fewest further moves;
that is, favors children having the fewest children.

kmoves←{
t←(,⍳⍵,⍵)∘.+↓8 2⍴2 1 2 ¯1 1 2 1 ¯2 ¯1 2 ¯1 ¯2 ¯2 1 ¯2 ¯1
(↓∧/(↑t)∊⍳⍵)/¨↓⍵⊥¨t
}
ktourw←{
M←↑kmoves ⍵
b←(⍵×⍵)⍴1
f←{(≢⍵)=≢M:⍵ ⋄ b[⊢/⍵]←0 ⋄ ∇⍵,(⊃⍋+/b[M[j;]])⌷j←{b[⍵]/⍵}M⌷⍨⊢/⍵}
(⍵,⍵)⍴⍋f 0
f←{b[⊢/⍵]←0 ⋄ ⍵,(⊃⍋+/b[M[j;]])⌷j←{b[⍵]/⍵}M⌷⍨⊢/⍵}
(⍵,⍵)⍴⍋f⍣(¯1+⍵*2)⊢0
}
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 less than 0.1 seconds.
Appeared in J in
[86]
and in APL in
[87].
