﻿ A History of APL in 50 Functions

<<   >>

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