nmats ← {sreq←1} ##.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).
Technical notes:
This is an example of a problem that 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
"each" (¨) operator.
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←{ ⍝ 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 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/(⌽,⍳⍵),⊂0⍴⊂⍬ ⍝ from each starting position.
}
Taking a line at a time:
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.
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:
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 its 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│
└───────────────────────┘
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│
└──────────┘
4 4⍴ ¯1 kt 3 4 ⍝ All 16 solutions for a 3x4 board.
┌──────────┬──────────┬──────────┬──────────┐
│ 1 4 7 10│1 4 7 10 │10 7 4 1│10 7 4 1 │
│12 9 2 5│8 11 2 5 │ 5 2 9 12│ 5 2 11 8 │
│ 3 6 11 8│3 6 9 12 │ 8 11 6 3│12 9 6 3 │
├──────────┼──────────┼──────────┼──────────┤
│12 9 6 3 │ 8 11 6 3│10 7 2 5│10 7 2 5 │
│ 1 4 11 8 │ 1 4 9 12│ 1 4 9 12│ 1 4 11 8 │
│10 7 2 5 │10 7 2 5│ 8 11 6 3│12 9 6 3 │
├──────────┼──────────┼──────────┼──────────┤
│3 6 9 12 │ 3 6 11 8│ 5 2 7 10│5 2 7 10 │
│8 11 4 1 │12 9 4 1│12 9 4 1│8 11 4 1 │
│5 2 7 10 │ 5 2 7 10│ 3 6 11 8│3 6 9 12 │
├──────────┼──────────┼──────────┼──────────┤
│3 6 9 12 │ 3 6 11 8│12 9 6 3 │ 8 11 6 3│
│8 11 2 5 │12 9 2 5│ 5 2 11 8 │ 5 2 9 12│
│1 4 7 10 │ 1 4 7 10│10 7 4 1 │10 7 4 1│
└──────────┴──────────┴──────────┴──────────┘
≡∘∪⍨ 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
⍝ Here is an alternative coding for a square board from Arthur Whitney:
kt_aw←{⎕io←0
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 ⍝ 8x8 board
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
⍝ ... and this from Roger Hui:
ktourw←{⎕io←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
⍝ See: http://www.jsoftware.com/jwiki/Essays/Knight's%20Tour
---------------------------------
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 2-row matrix,
whose first row is the board size and second (default: 1 .. 1 2) is the definit-
ion of the hyper-knight's moves. Notice the use of function →pmat← to generate a
permutation matrix.
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←×/⍴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.
}
(muse:
Solutions for high-rank boards appear to be much sparser than for matrices.
Perhaps this is due to the increase in the proportion of "hedged-in" cells,
those close to edges, as the rank increases. The sparsity of solutions is
greatly reduced if we play on an N-torus, where opposite (N-1)-faces of the
N-board are glued together. This could be achieved by changing line[6] in
the above function from:
net←(⊂,grid)∩¨↓grid∘.+∪,↓↑{ ⍝ absolute moves from each square.
to:
net←{ ⍝ absolute moves from each square.
⎕io+(⊂⊂bsize)|⍵-⎕io ⍝ opposite (N-1)-faces deemed adjacent.
}↓grid∘.+∪,↓↑{
whence:
⍕ disp¨ gkt¨(3 3)(4 4) ⍝ regular (1 2)-knight on small 2-tori.
┌─────┐ ┌───────────┐
│1 6 8│ │ 1 10 3 12│
│4 9 2│ │14 7 16 5│
│7 3 5│ │11 4 9 2│
└─────┘ │ 8 13 6 15│
└───────────┘
gkt 3 3 3 ⍝ (1 1 2)-knight on a 3-torus
┌────────┐
│ 1 6 8│
│15 17 10│
│26 19 24│
│ │
│18 11 13│
│20 22 27│
│ 4 9 2│
│ │
│23 25 21│
│ 7 3 5│
│12 14 16│
└────────┘
)
Examples:
gkt 8 8 ⍝ Tour of a regular board by a (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 5)(1 2 2) ⍝ Tour of a 4×5×5 board by a (1 2 2)-knight.
┌───────────────┐
│ 1 60 33 66 7│
│54 39 92 27 56│
│29 100 47 94 37│
│64 35 96 31 62│
│ 3 58 25 52 5│
│ │
│48 79 16 89 42│
│85 22 73 10 83│
│12 71 20 75 24│
│91 18 69 14 77│
│46 81 50 87 44│
│ │
│99 28 55 38 93│
│34 65 8 61 32│
│59 2 67 6 51│
│40 53 4 57 26│
│97 30 63 36 95│
│ │
│72 11 84 23 74│
│17 90 41 78 15│
│80 49 98 43 88│
│21 86 45 82 9│
│70 13 76 19 68│
└───────────────┘
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│
└─────┴─────┘
See also: queens pmat
Back to: contents
Back to: Workspaces