⍝ 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

Back to: code

Back to: Workspaces