nmats ← {sreq} ##.kt (rows cols) ⍝ Knight's Tour Chess Problem.
The challenge is to move a knight around the chessboard visiting each square
exactly once. The 2-vector right argument is the board size (rows and cols) and
the optional left argument is the number of solutions required (default 1).
Some technical points:
This is an example of a problem which is amenable to tree-searching. The knight
starts from each board square in turn, where he will have between 2 and 8
possibilities for his next "step" to a previously unvisited, let's call it
"k-adjacent", square. At each subsequent step he will have a choice of up to
8 moves until he has either visited all squares and so found a solution to the
problem, or all of his ways forward are blocked by already visited squares and
he has "painted himself into a corner". The choice of initial starting square,
together with the decisions facing him at each step on the way, can be visual-
ised as the forks of a dense branching tree.
The algorithm proceeds by trying at each step, EACH possible branch of the tree,
accumulating solutions when all squares have been visited and "backtracking"
when there is no way forward. This could be coded by applying the search
recursively at each step to each possible way forward using the primitive
operator _each_ ¨.
However, a small complication, which arises with this particular problem, is the
size of the tree. The number of knight's moves from each square on a standard
sized board is:
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
which means that to explore the complete tree would involve a number of steps
in the order of the product of these numbers: 9E43. See the examples below for
the number of solutions for some small-sized boards.
One possible way forward is to _display_ each solution as it is discovered using
⎕←···, and have the punter interrupt the process when s/he gets bored. An alter-
native approach, adopted here, is to specify how many solutions are required
(⍺←1) and exit from the process as soon as this many have been found. However,
this presents a further problem in that, at this point APL's state indicator
will contain ×/⍵ pendent _each_ ¨ operations which must be interrupted. A rather
clumsy way of achieving this would be to ⎕signal the vector of results back to
a receiving error-guard at the top level, thus bypassing the pending _eaches_ ¨.
The solution adopted here is to use primitive _reduction /_ instead of _each ¨_.
Reduction allows us to pass the vector of solutions-so-far as right argument and
each next step position in turn as left argument to the reduction's operand
function:
{operand-function} / step0, step1, ··· stepn, solutions-so-far
The difference is that with _reduction_, successive applications of the operand
function can be aware of the number of solutions accumulated by items to its
right in the reduction's argument, whereas with _each_, the items are processed
in isolation. In some sense, _each_ is parallel, while _reduce_ is sequential.
The reduction's operand function is coded to terminate as soon as it finds that
its right argument contains the required number of solutions. The reduction
continues to apply its operand with each remaining item as left argument but the
function now returns immediately without searching its tree-branch. By observat-
ion, this involves just 168 tests after the first solution for an 8×8 board.
A heuristic (sneaky trick) employed in the code is to find easy solutions first.
At each step, the following step that itself has the fewest available choices,
is examined first. This has the effect of making the knight "cling to the walls"
and eke out dark corners, leaving richer pickings in the centre of the board for
when things get tight later. Note that he will still find all solutions this
way, but they will become harder to find as the search progresses, rather than
being more evenly distributed throughout. The technique, suggested by H. C.
Warnsdorff in 1823, is known as "Warnsdorff's rule".
Coding details are as follows:
kt←{⎕ML←0 ⍝ Knight's Tour Chess Problem.
⍺←1 ⋄ sreq←⍺ ⋄ nsqs←×/⍵ ⍝ no of solutions required, default: 1.
kdef←,0 1∘.⌽1 ¯1∘.,2 ¯2 ⍝ vector of relative knight's moves.
net←(⊂,⍳⍵)∩¨↓(⍳⍵)∘.+kdef ⍝ absolute moves from each square.
⍳∘(⍳⍵)¨↑⍬{ ⍝ initially empty placement vector.
sreq=⍴⍵:⍵ ⍝ found enough 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/(⌽,⍳⍵),⊂0⍴⊂⍬ ⍝ from each starting position.
}
Taking a line at a time:
The code executes in migration-level 0, so that ↑ means mix.
As the number (⍺←1) of distinct solutions required and the total number of
squares are invariant for the whole of the search, it is convenient to assign
them names [sreq] and [nsqs] for reference from within the operand function.
[kdef] is a nested 8-vector of relative Knight's moves. The trivially easy
Rook's, King's, Queen's and the clearly impossible Bishop's and Pawn's, Tour
problems could be coded merely by changing [kdef] to reflect these pieces' rules
of play.
disp kdef
┌→──┬────┬────┬─────┬───┬────┬────┬─────┐
│1 2│1 ¯2│¯1 2│¯1 ¯2│2 1│¯2 1│2 ¯1│¯2 ¯1│
└~─→┴~──→┴~──→┴~───→┴~─→┴~──→┴~──→┴~───→┘
[net] is an ⍵-matrix representing the network of possible next positions from
each square on the board. Each cell contains a vector of the coordinates of its
k-adjacent squares. [net] is passed as an operand at each step in the search. As
the knight chooses his next step, the net is compressed to reflect squares that
are still available. The top left corner of the initial [net] for a standard
sized chessboard looks like this:
disp 3 3↑net
┌→────────────────┬─────────────────────────┬─────────────────────────────────┐
↓ ┌→──┬───┐ │ ┌→──┬───┬───┐ │ ┌→──┬───┬───┬───┐ │
│ │2 3│3 2│ │ │2 4│3 1│3 3│ │ │2 1│2 5│3 2│3 4│ │
│ └~─→┴~─→┘ │ └~─→┴~─→┴~─→┘ │ └~─→┴~─→┴~─→┴~─→┘ │
├────────────────→┼────────────────────────→┼────────────────────────────────→┤
│ ┌→──┬───┬───┐ │ ┌→──┬───┬───┬───┐ │ ┌→──┬───┬───┬───┬───┬───┐ │
│ │1 3│3 3│4 2│ │ │1 4│3 4│4 1│4 3│ │ │1 1│1 5│3 1│3 5│4 2│4 4│ │
│ └~─→┴~─→┴~─→┘ │ └~─→┴~─→┴~─→┴~─→┘ │ └~─→┴~─→┴~─→┴~─→┴~─→┴~─→┘ │
├────────────────→┼────────────────────────→┼────────────────────────────────→┤
│┌→──┬───┬───┬───┐│┌→──┬───┬───┬───┬───┬───┐│┌→──┬───┬───┬───┬───┬───┬───┬───┐│
││1 2│2 3│4 3│5 2│││1 1│1 3│2 4│4 4│5 1│5 3│││1 2│1 4│2 1│2 5│4 1│4 5│5 2│5 4││
│└~─→┴~─→┴~─→┴~─→┘│└~─→┴~─→┴~─→┴~─→┴~─→┴~─→┘│└~─→┴~─→┴~─→┴~─→┴~─→┴~─→┴~─→┴~─→┘│
└────────────────→┴────────────────────────→┴────────────────────────────────→┘
The unnamed body of code at the core of the search is a dyadic operator, whose
derived function is operand to the reduction.
↑⍬{ ⍝ initially empty placement vector.
···
}net/(⌽,⍳⍵),⊂0⍴⊂⍬ ⍝ from each starting position.
It is convenient to use an operator, as the values of both the current placement
vector and [net] are invariant for the duration of the reduction and so may be
bound per-reduction as operands and referenced as ⍺⍺ and ⍵⍵ respectively. In the
lower line above, the argument to the reduction is a vector (⌽,⍳⍵) of all poss-
ible starting positions followed by an initially empty result vector: 0⍴⊂⍬.
Within the body of the derived function:
sreq=⍴⍵:⍵ ⍝ found enough solutions: stop.
returns the result vector if enough solutions have been found. The next line
appends the next step to the current placement vector:
path←⍺⍺,⊂⍺ ⍝ extended placement vector.
If the path length is now equal to the number of squares on the board, the
knight has visited all squares and thus found a solution. The extended solutions
vector is returned as result:
(⍴path)=×/⍴net:⍵,⊂path ⍝ solution: accumulate.
The vector of next possible steps is extracted from the current net:
nxt←(⊂⍺)⊃⍵⍵ ⍝ moves from current square.
If there are no moves open to the knight, the current solutions vector is passed
along to the next item in the reduction to see if it has more luck:
0=⍴nxt:⍵ ⍝ stitched: back out.
Otherwise, if progress is still possible, a new [net] is calculated by removing
paths to the current square from each k-adjacent square.
net←⍵⍵~¨⊂⊂⍺ ⍝ compressed net.
The heuristic described above is applied by sorting remaining k-adjacent square
coordinates so that the one with the fewest exits is on the right and thus
visited first by the reduction.
ord←nxt[⍒↑⍴¨net[nxt]] ⍝ tightest-rightmost order.
The final line calls the operator recursively with newly-bound operands [path]
and [net] as operand to the reduction of the sorted next-step vector [ord].
Notice that because the operands are supplied explicitly, the recursive call is
on the operator _∇∇_, rather than it's derived function _∇_.
↑path ∇∇ net/ord,⊂⍵ ⍝ pursue remaining possibilities.
When the required number of results have been found, the ⍺-vector of (×/⍵)-paths
is converted into an ⍺-vector of index-origin-sensitive ⍵-matrices by the
function: ⍳∘(⍳⍵)¨.
Examples:
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
disp 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
8 11 2 5
3 6 9 12
disp ¯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↓
└~──────→┴~──────→┴~──────→┴~──────→┴~──────→┴~──────→┴~──────→┴~──────→┴~──────→┴~──────→┴~──────→┴~──────→┴~──────→┴~──────→┴~──────→┴~──────→┘
(⍳1000)≡{⍵⍳⍵}1000 kt 8 8 ⍝ First 1000 solutions are all distinct.
1
{⊃⍴¯1 kt ⍵}¨(⍳7 7)-⎕io ⍝ Number of solutions for some small boards.
0 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 16 0 0
0 0 0 16 0 164 1488
0 0 0 0 164 1728 37568
0 0 0 0 1488 37568 6637920
---------------------------------
The General Knight's Tour Problem
---------------------------------
It is characteristic of APL's generality with respect to array rank, that the
function can be extended to higher-rank chessboards, merely by defining the
relative moves for a "hyper-knight". For example, a "normal" (1 2)-knight moves
1 square in any of 4 directions, followed by 2 squares in either of 2 directions
perpendicular to the first move. By analogy, a (1 2 3)-knight on a rank-3 board,
moves 1 square in any of 6 directions, followed by 2 squares in any of 4 direct-
ions perpendicular to the first move, followed by 3 squares in either of 2
directions perpendicular to the first two moves.
In the generalised version [gkt], the right argument extends to a matrix, whose
first row is the board size and second row (default: 1 2) is the definition of
the hyper-knight's moves. Notice the use of function [pmat] to generate a perm-
utation matrix.
gkt←{⎕ML←0 ⍝ 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.
}
Examples:
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 ↑(4 5 6)(1 2 2) ⍝ Tour of a 4×5×6 board by a (1 2 2)-knight.
1 96 57 72 7 94
88 59 106 21 90 39
15 112 51 84 19 108
70 55 110 17 74 53
3 98 41 86 5 92
50 83 28 103 44 81
119 10 67 34 117 12
32 65 30 99 36 61
105 26 63 38 101 24
48 77 14 115 46 79
113 22 89 60 107 20
56 71 8 95 52 73
97 2 69 58 93 6
42 87 4 91 40 85
111 16 75 54 109 18
66 33 118 11 68 35
27 104 43 82 29 102
76 49 114 23 80 45
9 120 47 78 13 116
64 31 100 25 62 37
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
disp ¯1 gkt 2 1⍴3 1 ⍝ All tours of a 3 board by a 1-knight.
┌→────┬─────┐
│1 2 3│3 2 1│
└~───→┴~───→┘
See also: queens pmat
Back to: contents
Back to: Dyalog APL
Trouble seeing APL font?