```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│
└─────┴─────┘