⍝ 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
⍝∇ kt pmat
Back to: code
Back to: Workspaces