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←{⎕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 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:

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

⍝ Here is an alternative coding for a square board from Arthur Whitney:

      kt_aw←{⎕io ⎕ml←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 ⎕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

⍝ 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 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: Workspaces