```⍝ Knight's Tour Chess Problem:

⎕io←1

⍕kt 8 8                     ⍝ 1 tour around a standard 8×8 board.
1 26 15 24 29 50 13 32
16 23 28 51 14 31 64 49
27  2 25 30 63 60 33 12
22 17 52 59 44 57 48 61
3 42 21 56 53 62 11 34
18 39 54 43 58 45  8 47
41  4 37 20 55  6 35 10
38 19 40  5 36  9 46  7

3 kt 5 5                    ⍝ 3 tours around a smaller board.
┌──────────────┬──────────────┬──────────────┐
│ 1 12 25 18  7│ 1 12 23 18  7│ 1 12 23 18  7│
│22 17  8 13 24│22 17  8 13 24│24 17  8 13 22│
│11  2 23  6 19│11  2 25  6 19│11  2 21  6 19│
│16 21  4  9 14│16 21  4  9 14│16 25  4  9 14│
│ 3 10 15 20  5│ 3 10 15 20  5│ 3 10 15 20  5│
└──────────────┴──────────────┴──────────────┘

⍕kt 3 4                     ⍝ Tour around a non-square board.
1 4  7 10
12 9  2  5
3 6 11  8

¯1 kt 4 3                   ⍝ All solutions for a 4×3 board.
┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ 1 12  3│ 1  8  3│12  1 10│ 8  1 10│10  1 12│10  1  8│ 3 12  1│ 3  8  1│10  5 12│10  5  8│ 3 12  5│ 3  8  5│ 5 12  3│ 5  8  3│12  5 10│ 8  5 10│
│ 4  9  6│ 4 11  6│ 9  4  7│11  4  7│ 7  4  9│ 7  4 11│ 6  9  4│ 6 11  4│ 7  2  9│ 7  2 11│ 6  9  2│ 6 11  2│ 2  9  6│ 2 11  6│ 9  2  7│11  2  7│
│ 7  2 11│ 7  2  9│ 6 11  2│ 6  9  2│ 2 11  6│ 2  9  6│11  2  7│ 9  2  7│ 4 11  6│ 4  9  6│11  4  7│ 9  4  7│ 7  4 11│ 7  4  9│ 6 11  4│ 6  9  4│
│10  5  8│10  5 12│ 3  8  5│ 3 12  5│ 5  8  3│ 5 12  3│ 8  5 10│12  5 10│ 1  8  3│ 1 12  3│ 8  1 10│12  1 10│10  1  8│10  1 12│ 3  8  1│ 3 12  1│
└────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┘

gkt←{                               ⍝ General Knight's Tour Chess Problem.
⍺←1 ⋄ sreq←⍺                    ⍝ no. of solutions required, default: 1.
bsize kdefn←{                   ⍝ board size and moves definition.
1+(-⍴⍺)↑⍵-1                 ⍝ extend to left with 1's.
}\2↑(↓⍵),⊂1 2                   ⍝ default (1 2)-knight.
nsqs←×/bsize ⋄ grid←,¨⍳bsize    ⍝ number of squares and grid coords.
net←(⊂,grid)∩¨↓grid∘.+∪,↓↑{     ⍝ absolute moves from each square.
⍵[pmat⍴⍵]                   ⍝ all permutations of moves,
}∘,¨↑∘.,/1 ¯1∘×¨kdefn           ⍝ in each possible direction.
⍳∘grid¨↑⍬{                      ⍝ initially empty placement vector.
sreq=⍴⍵:⍵                   ⍝ found required no. of solutions: stop.
path←⍺⍺,⊂⍺                  ⍝ extended placement vector.
nsqs=⍴path:⍵,⊂path          ⍝ solution: accumulate.
nxt←(⊂⍺)⊃⍵⍵                 ⍝ moves from current square.
0=⍴nxt:⍵                    ⍝ stitched: back out.
net←⍵⍵~¨⊂⊂⍺                 ⍝ compressed net.
ord←nxt[⍒↑⍴¨net[nxt]]       ⍝ tightest-rightmost order.
↑path ∇∇ net/ord,⊂⍵         ⍝ pursue remaining possibilities.
}net/(⌽,grid),⊂0⍴⊂⍬             ⍝ from each starting position.
}

⍕gkt 8 8                    ⍝ Tour of standard board by normal (1 2)-knight.
1 26 15 24 29 50 13 32
16 23 28 51 14 31 64 49
27  2 25 30 63 60 33 12
22 17 52 59 44 57 48 61
3 42 21 56 53 62 11 34
18 39 54 43 58 45  8 47
41  4 37 20 55  6 35 10
38 19 40  5 36  9 46  7

⍕gkt 3 3 4 5                ⍝ Tour of a 3×3×4×5 board by a (1 1 1 2)-knight.
1 144  43  96  51
86 155  90 129  22
123  14 121  76 107
170  71 180  33 164

136  79 150  25 132
153  38 147  48  99
62 173  64 159  28
11 116  57 102  73

3 142  35  94  45
82 139  88 127  20
119   8 113  60 105
168  69 178  31 162

138  81 140  19 126
151   6 135  46  93
54 167  74 161  30
9 114  61 104  59

15 118  83 108  77
36 179  52 177  34
175   4 165  42  91
112  89 124  17 110

148  85 154  23 130
145  40 133  50  97
56 171  72 157  26
13 122  67 100  65

39 146  41  98  49
84 149  78 131  24
117  12 111  66 101
172  63 176  27 158

134  87 156  21 128
141   2 143  44  95
68 169  70 163  32
7 120  55 106  75

5 152  37  92  47
80 137  16 125  18
115  10 109  58 103
166  53 174  29 160

¯1 gkt ⍪3 1                 ⍝ All tours of a 3 board by a 1-knight.
┌─────┬─────┐
│1 2 3│3 2 1│
└─────┴─────┘

kt_aw←{⎕io←0                ⍝ Arthur's coding.
n←⍵
m←,0 1∘.⌽1 ¯1∘.,2 ¯2
m←{n⊥¨(⍵≡¨n|⍵)/⍵}¨↓(,⍳n n)∘.+m
k←{0<⍴⍵:⍵⋄(⍴m)=⍴x←⍺⍺,⍺:x⋄⊃x∇∇/z[⍒↑⍴¨m[z←(⍺⊃m)~x]~¨⊂x],⊂⍵}
n n⍴⍋0(⍬k)⍬
}

⍕kt_aw 8
0 57 14 31 48 27 12 29
15 32 53 62 13 30 49 26
58  1 56 45 54 47 28 11
33 16 61 52 63 44 25 50
2 59 42 55 46 51 10 39
17 34 19 60 43 40  7 24
20  3 36 41 22  5 38  9
35 18 21  4 37  8 23  6

⍝ Roger's coding:

ktourw←{⎕io ⎕ml←0  ⍝ Warnsdorff's algorithm for the (⍵,⍵) knight's tour
f←{⍵,c[{⍵⍳⌊/⍵}+/~⍺[c←⍺[⊃⌽⍵;]~⍵;]∊⍵]}
M←↑(↓∧/(↑t)∊⍳⍵)/¨↓⍵⊥¨t←(,⍳⍵,⍵)∘.+,0 1∘.⌽2 ¯2∘.,1 ¯1
(⍵,⍵)⍴⍋M f⍣(¯1+⍵×⍵),0
}

⍕ktourw 8
0 49 14 31 60 27 12 29
15 32 63 54 13 30 59 26
50  1 48 43 56 61 28 11
33 16 55 62 53 46 25 58
2 51 44 47 42 57 10 39
17 34 19 52 45 40  7 24
20  3 36 41 22  5 38  9
35 18 21  4 37  8 23  6

Back to: code

Back to: Workspaces
```