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 depth-first 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].