hp41programs

Knight

Knight's Tour for the HP41


Overview
 

 0°)  8 possible Moves+ A Subroutine
 1°)  Warndorff's Rule
 2°)  Closed Tours

  a)  4Kx8L Chessboards
  b)  5Kx6L Chessboards
  c)  6Kx6L Chessboards
  d)  6Kx7L Chessboards
  e)  7Kx8L Chessboards
  f)  7Kx10L Chessboards
  g)  8Kx5L Chessboards
  h)  8Kx8L Chessboards
  i)  10x3L Chessboards
  j)  12x3L Chessboards

 3°)  A Test: Do we Get a Tour ?
 4°)  Concatenation of 2 Closed Tours
 5°)  Transpose of an MxN Tour
 6°)  Displaying the results
 

>>>>  You may also find these programs - except "12*3L" - in the KNIGHTTOUR module which may be downloaded here
 

-The following routines return a sequence of Knight's moves on a  m x n  chessboard  so that each square of the board is visited exactly once.

-The first one uses Warnsdorff's method to find such a path. The next square is choosen among those that allow the least number of legal next moves.
-This method works very often - especially on small chessboards - but not always !

-The tours given by Warndorff's rule are open in most cases.
-Other specific programs always returns closed tours on chessboards of various sizes.
-They connect several copies of a basic closed tour to produce a closed tour on larger and larger chessboards.

-Since there are at most 319 data registers in the HP41, m x n must remains smaller than 319 ( SF 01 )
-However, you can also use a data file in the X-Memory modules to deal with larger chessboards, provided there are less than 600 squares ( SF 02 ).

-Alternatively, if you don't need to store the positions, they may be successively displayed ( SF 00 ).

-The squares of the board are numbered in column order.
-For instance, the Knight's moves on a 5 x 6 chessboard are stored in registers

        R01   R06   R11   R16   R21   R26
        R02   R07   R12   R17   R22   R27
        R03   R08   R13   R18   R23   R28
        R04   R09   R14   R19   R24   R29
        R05   R10   R15   R20   R25   R30
 

Important Notes about Flags:
 

 In most cases:

  SF 00  displays the successive moves
  SF 01  stores the positions in data registers
  SF 02  stores the positions in an X-memory data file - which must be the current file

-So, if flags F00  F01  F02 are clear... nothing may happen !

  CF 04  displays PROMPT's

-Thus, if flag F04 is set, you can call these programs as subroutines without problems
 

0°)  8 Possible Moves + A Subroutine
 

-The 8 subroutines "M1" ..... "M8"  performs the 8 knight's moves as shown below:
 
 

  M1  M8
 M2  M7
  K
 M3  M6
 M4  M5

 
 
 01  LBL "M1"
 02  RCL 00
 03  INT
 04  -
 05  2
 06  -
 07  X<>Y
 08  1
 09  +
 10  GTO 00      
 11  LBL "M2"
 12  RCL 00
 13  INT
 14  ST+ X
 15  -
 16  1
 17  ST+ Z
 18  -
 19  X<>Y		  20  GTO 00
 21  LBL "M3"
 22  RCL 00
 23  INT
 24  ST+ X
 25  -
 26  1
 27  ST+ Z
 28  +
 29  X<>Y
 30  GTO 00      
 31  LBL "M4"
 32  RCL 00
 33  INT
 34  -
 35  2
 36  +
 37  X<>Y
 38  1		  39  +
 40  GTO 00
 41  LBL "M5"
 42  RCL 00
 43  INT
 44  +
 45  2
 46  +
 47  X<>Y
 48  1
 49  +
 50  GTO 00      
 51  LBL "M6"
 52  RCL 00
 53  INT
 54  ST+ X
 55  +
 56  1
 57  ST+ Z		  58  +
 59  X<>Y
 60  GTO 00
 61  LBL "M7"
 62  RCL 00      
 63  INT
 64  ST+ X
 65  +
 66  1
 67  ST+ Z
 68  -
 69  X<>Y
 70  GTO 00
 71  LBL "M8"
 72  RCL 00
 73  INT
 74  +
 75  2
 76  -		  77  X<>Y
 78  ISG X
 79  LBL 00      
 80  FS? 01
 81  STO IND Y
 82  X<>Y
 83  FC? 00
 84  GTO 00      
 85  VIEW X
 86  FC? 21
 87  PSE
 88  LBL 00
 89  FC? 02
 90  RTN
 91  SEEKPT
 92  X<>Y
 93  SAVEX
 94  X<>Y
 95  END

 
-They take the number N of the previous move in Y-register and the previous position of the knight in X-register
  and return N+1 in Y-register and the new position in X-register

-If F00 is set, the new position is displayed
-If F01 is set, the new position is stored in the corresponding data register
-If F02 is set, the new position is stored in the data file

-R00 must contain a number whose integer part = number of rows.
-These routines do not check if the move is legal or not, inside the chessboard or not.

-Another subroutine is also used to save bytes ( it's called "^" in the KNIGHTTOUR module ):
 
 

 01  LBL "IN"
 02  STO 00
 03  RDN
 04  " K^L"
 05  FC? 04
 06  PROMPT
 07  CF 10
 08  STO N
 09  STO O
 10  RDN
 11  ST* 00
 12  1
 13  X=Y?
 14  SF 10
 15  -
 16  STO M
 17  CLX
 18  FS? 02
 19  SEEKPT
 20  END

 
-It's called at the beginning of many programs
 

1°)  Warndorff's Rule
 

 "WARN" employs Warndorff's rule to try to create a knight tour on a MxN chessboard
 Though it works in most cases - at least on "small" chessboards - it may fail sometimes

 If the program returns in X a number equal to M.N , you've got a Tour
 Otherwise, there will be at least 1 unvisited square.
 

Data Registers:          R00 = m.nnn

                                     R01 thru R32 are used for tmporary data storage
                                     The chessboard is stored in R33 thru R32+m.n  during the calculations

               >>>>   When the program stops, the chessboard is in registers R01 thru Rm.n              ( R00 is unchanged )

Flags: /
Subroutines: /
 
 

 01  LBL "WARN"
 02  CLRG
 03  " M^N^K1?"
 04  FC? 04
 05  PROMPT
 06  STO T
 07  X<> Z
 08  STO 14
 09  X<>Y
 10  STO 00       
 11  *
 12  32
 13  ST+ Z
 14  STO 10
 15  STO 12
 16  STO 15
 17  +
 18  STO 09
 19  X<>Y
 20  STO 01
 21  SIGN
 22  STO 08
 23  ST+ 10
 24  STO IND L
 25  STO 18		  26  STO 23
 27  CHS
 28  STO 19
 29  STO 22
 30  2
 31  STO 17
 32  STO 24
 33  CHS
 34  STO 20       
 35  STO 21
 36  RCL 14
 37  +
 38  STO 25
 39  CHS
 40  STO 29
 41  4
 42  -
 43  STO 32
 44  CHS
 45  STO 28
 46  ST+ X
 47  3
 48  -
 49  STO 27
 50  CHS		  51  STO 31
 52  2
 53  +
 54  STO 30
 55  CHS
 56  STO 26
 57  24.016
 58  STO 11
 59  STO 16       
 60  8
 61  STO 13
 62  LBL 01
 63  RCL 01
 64  RCL 12
 65  -
 66  FS? 00
 67  VIEW X
 68  1
 69  -
 70  RCL 14
 71  MOD
 72  STO 02
 73  9
 74  STO 03
 75  LBL 02		  76  RCL 09
 77  RCL 01
 78  RCL IND 12
 79  +
 80  X>Y?
 81  GTO 04
 82  STO 04
 83  RCL 10       
 84  X>Y?
 85  GTO 04
 86  -
 87  RCL 14
 88  MOD
 89  STO 05
 90  RCL IND 11
 91  +
 92  RCL 02
 93  X#Y?
 94  GTO 04
 95  RCL IND 04
 96  X#0?
 97  GTO 04
 98  CLX
 99  STO 07
100  LBL 03		 101  RCL 09
102  RCL 04       
103  RCL IND 15
104  +
105  X>Y?
106  GTO 00
107  STO Y
108  RCL 10
109  X>Y?
110  GTO 00
111  -
112  RCL 14
113  MOD
114  RCL IND 16
115  +
116  RCL 05
117  X#Y?
118  GTO 00
119  RCL IND Z
120  X=0?
121  ISG 07
122  LBL 00
123  DSE 15
124  DSE 16
125  GTO 03		 126  RCL 13
127  ST+ 15
128  ST+ 16
129  RCL 07
130  RCL 03
131  X<=Y?
132  GTO 04
133  X<>Y
134  STO 03
135  RCL 04
136  STO 06       
137  LBL 04
138  DSE 12
139  DSE 11
140  GTO 02
141  RCL 13
142  ST+ 11
143  ST+ 12
144  RCL 03
145  9
146  X=Y?
147  GTO 00
148  RCL 06
149  STO 01
150  SIGN		 151  ST+ 08
152  RCL 08
153  STO IND 01
154  GTO 01
155  LBL 00
156  RCL 08       
157  RCL 00
158   E3
159  /
160  STO 00
161  RCL 14
162  ST+ 00
163  *
164   E3
165  /
166  33.001
167  +
168  REGMOVE
169  RDN
170  CLD
171  END

 
           ( 260 bytes / SIZE 33+M.N )
 
 

      STACK        INPUTS      OUTPUTS
           Z            M             /
           Y            N             /
           X            K1            V

               M = number of rows
   where   N = number of columns
               K1 is the initial position of the Knight and V = number of visited squares.

-If  V = M.N ,   the tour is complete
-If  V < M.N ,  one ( or several ) square(s) remain(s) unvisited

Example1:    On a classical  8 x 8  chessboard,   M = N = 8  and if you choose  K1 = 1

        CF 04  XEQ "WARN"   M^N^K1?

   8   ENTER^
        ENTER^
   1      R/S      >>>>   64                                                           ---Execution time = 22mn24s---

   X-output = 64 = 8x8.  So, the Knight has made a complete tour and we find in registers R01 thru R64:
 

         R01   R09   R17   R25   R33   R41   R49   R57                                    1    26   15   24   29   34   13   32
         R02   R10   R18   R26   R34   R42   R50   R58                                   16   23   28   37   14   31   64   35
         R03   R11   R19   R27   R35   R43   R51   R59                                   27    2    25   30   61   36   33   12
         R04   R12   R20   R28   R36   R44   R52   R60                =                 22   17   40   49   38   55   60   63
         R05   R13   R21   R29   R37   R45   R53   R61                                    3    48   21   56   41   62   11   54
         R06   R14   R22   R30   R38   R46   R54   R62                                   18   45   42   39   50   53    8    59
         R07   R15   R23   R31   R39   R47   R55   R63                                   43    4    47   20   57    6    51   10
         R08   R16   R24   R32   R40   R48   R56   R64                                   46   19   44    5    52    9    58    7
 
 
 

  1  26  15  24  29  34  13  32
 16  23  28  37  14  31  64  35
 27   2  25  30  61  36  33  12
 22  17  40  49  38  55  60  63
  3  48  21  56  41  62  11  54
 18  45  42  39  50  53   8  59
 43   4  47  20  57   6  51  10
 46  19  44   5  52   9  58   7

 
-If you set flag F00 before executing "WARN" , the HP41 displays the successive positions:

   1  11  5  15  40  ...............  60  50  and finally  64 = number of visited squares.

-If flag F04 is set, place directly the required inputs in the stack:

   8   ENTER^
        ENTER^
   1   XEQ "WARN"    >>>>   64
 

Example2:     On a 3 x 4 chessboard  if you choose  K1 = 1
 

       XEQ "WARN"         M^N^K1?

       3  ENTER  4  ENTER  1  R/S  >>>   12                                                    ---Execution time = 2m15s---

  X-output = 12   and we have:

        R01   R04   R07   R10                   1   4   7  10
        R02   R05   R08   R11       =          8  11  2   5
        R03   R06   R09   R12                   3   6   9  12
 
 

  1   4   7  10
  8  11   2   5
  3   6   9  12

 
Notes:

-This program always fails if  m = n  and  1 < m < 5 - logical since there is no solution !
-If  m = n > 4 , a complete tour is generally ( but not always ) found:

-For instance, with m = n = 8 , there is a unique exception:   K1 = 30  does not produce a tour.

>>>  If you choose  s1 = 7  a complete tour is always returned when n = m = 5 , 6 , ................... , 16.

-Though this routine doesn't seek closed Tours, it may find one from time to time:
-For example, on a  6 x 6 chessboard, s1 = 25 gives a closed tour.
-Closed Tours are impossible on a  m x m chessboard if m is odd.
 

2°)  Closed Tours
 

    a)  4Kx8L Chessboards
 

-"4K*8L" uses the method described in reference [2] - with minor differences - to produce a closed tour on an MxN chessboard
  with M = 4K & N = 8L ( K > 1 )
-If K = 2, you must choose L = 1 ( otherwise, you get a DATA ERROR message )

-But if you want a closed tour on an 8x12 chessboard, swap m & n and key in K = 3 & L = 1

-When the program stops, M.NNN is stored in R00
 

Data Registers:          R00 = m.nnn

Flags:  SF 00 <-> the moves are successively displayed
            SF 01 <-> the moves are successively stored in data registers R01 thru Rm.n
            SF 02 <-> the moves are successively stored in the current data file ( size at least m.n+1 )

            SF 04 <-> no prompt

Subroutines:  "M1" "M2" ......  "M8"
 
 

 01 LBL "4K*8L"
 02 " K>1^L"
 03 FC? 04
 04 PROMPT
 05 ST+ X
 06 STO N
 07 X<>Y
 08 STO 00
 09 STO M
 10 2
 11 X#Y?
 12 GTO 00
 13 RDN
 14 X#Y?
 15 ACOS
 16 LBL 00
 17 RCL 00
 18 0
 19 FS? 02
 20 SEEKPT
 21 RCL Y
 22 4
 23 ST* 00
 24 ST+ X
 25 *
 26 DSE X
 27 LBL 09
 28 XROM "M5"
 29 XROM "M3"
 30 XROM "M4"
 31 XROM "M7"
 32 DSE Z
 33 GTO 09
 34 RCL N
 35 2
 36 -
 37 X=0?
 38 GTO 00
 39 STO T
 40 RDN
 41 LBL 10
 42 XROM "M6"
 43 XROM "M8"
 44 XROM "M7"
 45 XROM "M4"
 46 DSE Z
 47 GTO 10
 48 ENTER
 49 LBL 00
 50 CLX
 51 RCL 00
 52 1
 53 +
 54 3
 55 *
 56 +
 57 RCL M
 58 STO T
 59 RDN
 60 LBL 11
 61 XROM "M1"
 62 XROM "M7"
 63 XROM "M8"
 64 XROM "M3"
 65 DSE Z
 66 GTO 11
 67 RCL N		  68 2
 69 /
 70 1
 71 -
 72 X=0?
 73 GTO 41
 74 STO O
 75 RDN
 76 LBL 01
 77 XROM "M2"
 78 XROM "M3"
 79 XROM "M4"
 80 XROM "M7"
 81 RCL M
 82 3
 83 -
 84 X=0?
 85 GTO 00
 86 STO T
 87 RDN
 88 LBL 12
 89 XROM "M5"
 90 XROM "M3"
 91 XROM "M4"
 92 XROM "M7"
 93 DSE Z
 94 GTO 12
 95 ENTER
 96 LBL 00
 97 RDN
 98 XROM "M5"
 99 XROM "M4"
100 XROM "M3"
101 XROM "M8"
102 XROM "M2"
103 XROM "M4"
104 XROM "M3"
105 XROM "M8"
106 RCL M
107 2
108 -
109 STO T
110 RDN
111 LBL 13
112 XROM "M1"
113 XROM "M7"
114 XROM "M8"
115 XROM "M3"
116 DSE Z
117 GTO 13
118 DSE O
119 GTO 01
120 ENTER
121 LBL 41
122 RDN
123 XROM "M3"
124 XROM "M1"
125 XROM "M3"
126 XROM "M5"
127 RCL M
128 2
129 -
130 X=0?
131 GTO 00
132 STO T
133 RDN
134 LBL 14		 135 XROM "M4"
136 XROM "M7"
137 XROM "M5"
138 XROM "M3"
139 DSE Z
140 GTO 14
141 ENTER
142 LBL 00
143 RDN
144 XROM "M4"
145 XROM "M5"
146 XROM "M7"
147 XROM "M1"
148 RCL N
149 DSE X
150 STO T
151 RDN
152 LBL 02
153 XROM "M6"
154 XROM "M5"
155 XROM "M7"
156 XROM "M1"
157 DSE Z
158 GTO 02
159 RCL M
160 2
161 -
162 X=0?
163 GTO 00
164 STO T
165 RDN
166 LBL 03
167 XROM "M8"
168 XROM "M3"
169 XROM "M1"
170 XROM "M7"
171 DSE Z
172 GTO 03
173 ENTER
174 LBL 00
175 RDN
176 XROM "M8"
177 XROM "M1"
178 XROM "M3"
179 XROM "M5"
180 RCL N
181 2
182 /
183 1
184 -
185 X=0?
186 GTO 41
187 STO O
188 RDN
189 LBL 04
190 XROM "M2"
191 XROM "M1"
192 XROM "M3"
193 XROM "M5"
194 RCL M
195 2
196 -
197 STO T
198 RDN
199 LBL 05
200 XROM "M4"
201 XROM "M7"		 202 XROM "M5"
203 XROM "M3"
204 DSE Z
205 GTO 05
206 XROM "M2"
207 XROM "M3"
208 XROM "M1"
209 XROM "M7"
210 RCL M
211 3
212 -
213 X=0?
214 GTO 00
215 STO T
216 RDN
217 LBL 06
218 XROM "M8"
219 XROM "M3"
220 XROM "M1"
221 XROM "M7"
222 DSE Z
223 GTO 06
224 ENTER
225 LBL 00
226 RDN
227 XROM "M8"
228 XROM "M1"
229 XROM "M3"
230 XROM "M5"
231 DSE O
232 GTO 04
233 ENTER
234 LBL 41
235 CLX
236 RCL 00
237 ST+ X
238 +
239 RCL N
240 2
241 /
242 1
243 -
244 X=0?
245 GTO 41
246 STO O
247 RDN
248 LBL 07
249 RCL M
250 2
251 -
252 STO T
253 RDN
254 LBL 08
255 XROM "M4"
256 XROM "M2"
257 XROM "M5"
258 XROM "M6"
259 DSE Z
260 GTO 08
261 XROM "M7"
262 XROM "M6"
263 XROM "M1"
264 XROM "M2"
265 RCL M
266 3
267 -
268 X=0?		 269 GTO 00
270 STO T
271 RDN
272 LBL 20
273 XROM "M8"
274 XROM "M6"
275 XROM "M1"
276 XROM "M2"
277 DSE Z
278 GTO 20
279 ENTER
280 LBL 00
281 RDN
282 XROM "M8"
283 XROM "M1"
284 XROM "M6"
285 XROM "M5"
286 XROM "M7"
287 XROM "M1"
288 XROM "M6"
289 XROM "M5"
290 DSE O
291 GTO 07
292 ENTER
293 LBL 41
294 CLX
295 RCL M
296 2
297 -
298 X=0?
299 GTO 00
300 STO T
301 RDN
302 LBL 21
303 XROM "M4"
304 XROM "M2"
305 XROM "M5"
306 XROM "M6"
307 DSE Z
308 GTO 21
309 ENTER
310 LBL 00
311 CLX
312 RCL 00
313 +
314 1
315 +
316 RCL N
317 STO T
318 RDN
319 LBL 22
320 XROM "M3"
321 XROM "M5"
322 XROM "M2"
323 XROM "M1"
324 DSE Z
325 GTO 22
326 RCL M
327 2
328 -
329 X=0?
330 GTO 00
331 STO T
332 RDN
333 LBL 23
334 XROM "M8"
335 XROM "M6"		 336 XROM "M1"
337 XROM "M2"
338 DSE Z
339 GTO 23
340 ENTER
341 LBL 00
342 RDN
343 XROM "M8"
344 XROM "M1"
345 XROM "M6"
346 XROM "M5"
347 XROM "M7"
348 XROM "M1"
349 XROM "M6"
350 XROM "M5"
351 RCL 00
352 INT
353 3
354 *
355 -
356 DSE X
357 RCL N
358 2
359 /
360 1
361 -
362 X=0?
363 GTO 41
364 STO O
365 RDN
366 LBL 96
367 RCL M
368 3
369 -
370 X=0?
371 GTO 00
372 STO T
373 RDN
374 LBL 24
375 XROM "M5"
376 XROM "M6"
377 XROM "M4"
378 XROM "M2"
379 DSE Z
380 GTO 24
381 ENTER
382 LBL 00
383 RDN
384 XROM "M5"
385 XROM "M4"
386 XROM "M6"
387 XROM "M8"
388 XROM "M7"
389 XROM "M4"
390 XROM "M6"
391 XROM "M8"
392 RCL M
393 2
394 -
395 STO T
396 RDN
397 LBL 25
398 XROM "M1"
399 XROM "M2"
400 XROM "M8"
401 XROM "M6"
402 DSE Z		 403 GTO 25
404 XROM "M7"
405 XROM "M6"
406 XROM "M4"
407 XROM "M2"
408 DSE O
409 GTO 96
410 ENTER
411 LBL 41
412 CLX
413 RCL M
414 DSE X
415 STO T
416 RDN
417 LBL 26
418 XROM "M5"
419 XROM "M6"
420 XROM "M4"
421 XROM "M2"
422 DSE Z
423 GTO 26
424 RCL N
425 2
426 -
427 X=0?
428 GTO 00
429 STO T
430 RDN
431 LBL 27
432 XROM "M3"
433 XROM "M8"
434 XROM "M2"
435 XROM "M4"
436 DSE Z
437 GTO 27
438 ENTER
439 LBL 00
440 CLX
441 3
442 +
443 RCL 00
444 INT
445 -
446 RCL M
447 STO T
448 RDN
449 LBL 28
450 XROM "M1"
451 XROM "M2"
452 XROM "M8"
453 XROM "M6"
454 DSE Z
455 GTO 28
456 XROM "M7"
457 XROM "M6"
458 XROM "M4"
459 XROM "M2"
460 RCL N
461 250
462 /
463 RCL 00
464 +
465 STO 00
466 CLA
467 END

 
      ( 789 bytes / SIZE 001 or 1+4Kx8L )
 
 

      STACK        INPUTS      OUTPUTS
           Y            K             /
           X            L       M.NNN

 
Example1:   A closed tour on a classical 8x8 chessboard

   SIZE 065 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "4K*8L"   >>>   K>1^L

    2  ENTER  1  R/S  >>>   8.008 = R00                                                      ---Execution time = 37s---

And you find in registers R01 thru R64
 
 

  42   59   18    1   46   61   30   15
  19    2   43   60   31   16   47   62
  58   41    4   17   64   45   14   29
   3   20   57   44   13   32   63   48
  40   55   24    5   36   49   28   11
  21    6   37   56   25   12   33   50
  54   39    8   23   52   35   10   27
   7   22   53   38    9   26   51   34

 
Example2:   A closed tour on a 16x24 chessboard
 

-Create a data file ( size at least 384+1 = 385 )

   CF 00  CF 01  SF 02   CF 04  XEQ "4K*8L"   >>>   K>1^L

    4  ENTER  3   R/S   >>>   16.024 = R00                                                      ---Execution time = 4m59s---

And the data file - ignoring the 1st data - contains:
 
 

 282  379   98    1  286  381  190   95  210  307  170   73  214  309  166   71  234  331  146   49  238  333  142   47
  99    2  283  380  191   96  287  382  171   74  211  308  167   72  215  310  147   50  235  332  143   48  239  334
 378  281    4   97  384  285   94  189  306  209   76  169  312  213   70  165  330  233   52  145  336  237   46  141
   3  100  377  284   93  192  383  288   75  172  305  212   69  168  311  216   51  148  329  236   45  144  335  240
 280  375  102    5  194  289  188   91  208  303  174   77  218  313  164   67  232  327  150   53  242  337  140   43
 101    6  279  376  187   92  193  290  173   78  207  304  163   68  217  314  149   54  231  328  139   44  241  338
 374  277    8  103  292  195   90  185  302  205   80  175  316  219   66  161  326  229   56  151  340  243   42  137
   7  104  373  278   89  186  291  196   79  176  301  206   65  162  315  220   55  152  325  230   41  138  339  244
 276  371  106    9  198  293  184   85  204  297  178   81  222  317  160   61  228  321  154   57  246  341  136   39
 105   10  275  372  183   88  197  296  177   84  203  300  159   64  221  320  153   60  227  324  135   40  245  342
 370  273   12  107  294  199   86  181  298  201   82  179  318  223   62  157  322  225   58  155  344  247   38  133
  11  108  369  274   87  182  295  200   83  180  299  202   63  158  319  224   59  156  323  226   37  134  343  248
 272  367  112   13  268  363  116   19  264  359  120   23  260  355  124   27  256  351  128   31  252   345  132   35
 109   14  269  368  113   18  265  362  117   22  261  358  121   26  257  354  125   30  253  350  129   36  249  346
 366  271   16  111  364  267   20  115  360  263   24  119  356  259   28  123  352  255   32  127  348  251   34  131
  15  110  365  270   17  114  361  266   21  118  357  262   25  122  353  258   29  126  349  254   33  130  347  250

 
Method:

-The whole chessboard is divided in 4x4 squares symbolized by a letter, here from A to X

     A  X   S   R  M   L
     B  W  T   Q  N  K
     C  V   U   P  O   J
     D   E   F   G  H   I

-The knight fills the squares in the "letter" A like this:

     *  *  *  1
     *  2  *  *
     *  *  4  *       and continues in a similar way in alphabetical order until letter X ( 93 94 95 96 )
     3  *  *  *

-Then, the path A B ..... X is used again but the knight fills the squares in the letter A like this:

    *   *  98  *
   99  *   *   *
    *   *   *  97    and continues in a similar way until letter X ( 189 190 191 192 )
    * 100 *   *

-Then, there is a change in the direction: the path becomes W V U ..... B A X  with the pattern:

   194   *    *    *
     *     *  193  *
     *   195  *    *     similar way until the letter X  ( 285 286 287 288 )
     *     *    *  196

-Finally, following again the path W V U ..... B A X, the remaining squares are filled with the pattern:

    *   289   *    *
    *     *     *  290
  292   *     *    *     until the "letter" X  ( 381 382 383 384 )   and the closed tour is completed !
    *     *   291  *
 

    b)  5Kx6L Chessboards
 

-In the following routines, we use a different method:
-Here, a closed tour on a 5x6 chessboard is the basis.
-And several copies of this tour are connected to produce a larger tour
 

Data Registers:          R00 = m.nnn

Flags:  SF 00 <-> the moves are successively displayed
            SF 01 <-> the moves are successively stored in data registers R01 thru Rm.n
            SF 02 <-> the moves are successively stored in the current data file ( size at least m.n+1 )

            SF 04 <-> no prompt

Subroutines:  "M1" "M2" ......  "M8"  "IN"
 
 

 01 LBL "5K*6L"
 02 5
 03 XROM "IN"
 04 4
 05 RCL 00
 06 ST+ X
 07 -
 08 LBL 09
 09 RCL M
 10 STO T
 11 RDN
 12 XROM "M7"
 13 XROM "M5"
 14 XROM "M8"
 15 XROM "M3"
 16 XROM "M6"
 17 FS? 10
 18 GTO 00
 19 LBL 10
 20 XROM "M4"		  21 XEQ 13
 22 DSE Z
 23 GTO 10
 24 RCL M
 25 STO T
 26 RDN
 27 XROM "M7"
 28 XROM "M8"
 29 XROM "M2"
 30 LBL 11
 31 XROM "M8"
 32 DSE Z
 33 X=0?
 34 GTO 00
 35 XROM "M8"
 36 XROM "M2"
 37 GTO 11
 38 LBL 00
 39 FS? 10
 40 XROM "M7"		  41 DSE N
 42 GTO 09
 43 XROM "M8"
 44 RCL O
 45 STO N
 46 CLX
 47 RCL 00
 48 ST+ X
 49 DSE X
 50 +
 51 DSE Y
 52 LBL 12
 53 XROM "M3"
 54 XROM "M2"
 55 XROM "M3"
 56 XEQ 14
 57 DSE N
 58 GTO 12
 59 GTO 04
 60 LBL 13		  61 XEQ 14
 62 XROM "M4"
 63 XROM "M5"
 64 XROM "M8"
 65 XROM "M3"
 66 XROM "M6"
 67 RTN
 68 LBL 14
 69 XROM "M5"
 70 XROM "M3"
 71 XROM "M8"
 72 XROM "M1"
 73 XROM "M6"
 74 XROM "M7"
 75 XROM "M5"
 76 XROM "M4"
 77 XROM "M1"
 78 XROM "M1"
 79 XROM "M3"
 80 XROM "M5"		  81 XROM "M6"
 82 XROM "M7"
 83 XROM "M1"
 84 XROM "M4"
 85 XROM "M6"
 86 XROM "M1"
 87 XROM "M8"
 88 XROM "M3"
 89 XROM "M2"
 90 RTN
 91 LBL 04
 92 RCL O
 93 .006
 94 *
 95 RCL 00
 96 +
 97 STO 00
 98 CLA
 99 END

 
    ( 186 bytes / SIZE 001 or 1+5Kx6L )
 
 

      STACK        INPUTS      OUTPUTS
           Y            K             /
           X            L       M.NNN

 
Example1:   A closed tour on a 5x6 chessboard

   SIZE 031 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "5K*6L"   >>>   K^L

    1  ENTER  (1)  R/S  >>>   5.006 = R00                                                      ---Execution time = 16s---

And you find in registers R01 thru R30
 
 

 13  30  19   8  15  28
 20   9  14  29  24   7
  1  12   3  18  27  16
  4  21  10  25   6  23
 11   2   5  22  17  26

 
Example2:   A closed tour on a 15x12 chessboard

    SIZE 181 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "5K*6L"   >>>   K^L

    3  ENTER  2  R/S  >>>   15.012 = R00                                                      ---Execution time = 87s---

And you find in registers R01 thru R180
 
 

 163  180  169  158  165  178  139  156  145  134  141  154
 170  159  164  179  174  157  146  135  140  155  150  133
   1  162    3  168  177  166   67  138   69  144  153  142
   4  171  160  175   66  173   70  147  136  151  132  149
 161    2    5  172  167  176  137   68   71  148  143  152
  10   27   16   65   12   25   76   93   82  131   78   91
  17    6   11   26   21   64   83   72   77   92   87  130
  28    9   30   15   24   13   94   75   96   81   90   79
  31   18    7   22   63   20   97   84   73   88  129   86
   8   29   32   19   14   23   74   95   98   85   80   89
  37   54   43   62   39   52  103  120  109  128  105  118
  44   33   38   53   48   61  110   99  104  119  114  127
  55   36   57   42   51   40  121  102  123  108  117  106
  58   45   34   49   60   47  124  111  100  115  126  113
  35   56   59   46   41   50  101  122  125  112  107  116

 
Note:

-When the program stops, M.NNN is stored in R00
 

    c)  6Kx6L Chessboards
 

-A closed tour on a 6x6 chessboard is the basis.
-And several copies of this tour are connected to produce a larger tour
 

Data Registers:          R00 = m.nnn

Flags:  SF 00 <-> the moves are successively displayed
            SF 01 <-> the moves are successively stored in data registers R01 thru Rm.n
            SF 02 <-> the moves are successively stored in the current data file ( size at least m.n+1 )

            SF 04 <-> no prompt

Subroutines:  "M1" "M2" ......  "M8"  "IN"
 
 

 01 LBL "6K*6L"
 02 6
 03 XROM "IN"
 04 4
 05 RCL 00
 06 -
 07 LBL 01
 08 RCL M
 09 STO T
 10 RDN
 11 XROM "M7"
 12 XEQ 14
 13 FS? 10
 14 GTO 09
 15 LBL 02
 16 XROM "M4"
 17 XROM "M6"
 18 XROM "M5"
 19 XROM "M4"
 20 XEQ 13
 21 XROM "M8"		  22 XEQ 14
 23 DSE Z
 24 GTO 02
 25 RCL M
 26 STO T
 27 RDN
 28 XROM "M3"
 29 XEQ 12
 30 LBL 03
 31 XROM "M8"
 32 LBL 09
 33 FS? 10
 34 XROM "M3"
 35 XEQ 12
 36 DSE Z
 37 GTO 03
 38 XROM "M7"
 39 XROM "M6"
 40 XROM "M5"
 41 DSE N
 42 GTO 01		  43 XROM "M4"
 44 RCL O
 45 STO N
 46 CLX
 47 RCL 00
 48 INT
 49 ST+ X
 50 DSE X
 51 +
 52 DSE Y
 53 LBL 04
 54 XROM "M3"
 55 XEQ 13
 56 DSE N
 57 GTO 04
 58 GTO 09
 59 LBL 12
 60 XROM "M8"
 61 XROM "M2"
 62 XROM "M5"
 63 XROM "M6"		  64 XROM "M7"
 65 XROM "M1"
 66 XROM "M8"
 67 XROM "M3"
 68 XROM "M2"
 69 XROM "M5"
 70 XROM "M3"
 71 XROM "M6"
 72 XROM "M3"
 73 XROM "M8"
 74 XROM "M1"
 75 RTN
 76 LBL 13
 77 XROM "M1"
 78 XROM "M7"
 79 XROM "M4"
 80 XROM "M3"
 81 XROM "M2"
 82 RTN
 83 LBL 14
 84 XROM "M1"		  85 XROM "M6"
 86 XROM "M7"
 87 XROM "M4"
 88 XROM "M2"
 89 XROM "M7"
 90 XROM "M6"
 91 XROM "M4"
 92 XROM "M5"
 93 XROM "M2"
 94 RTN
 95 LBL 09
 96 RCL O
 97 .006
 98 *
 99 RCL 00
100 +
101 STO 00
102 CLA
103 END

 
      ( 195 bytes / SIZE 001 or 1+6Kx6L )
 
 

      STACK        INPUTS      OUTPUTS
           Y            K             /
           X            L       M.NNN

 
Example1:   A closed tour on a 6x6 chessboard

   SIZE 037 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "6K*6L"   >>>   K^L

    1  ENTER   R/S  >>>   6.006 = R00                                                      ---Execution time = 19s---

And you find in registers R01 thru R36
 
 

  2  21  28   7   4  19
 27   6   3  20  29   8
 14   1  22   5  18  33
 23  26  13  32   9  30
 36  15  24  11  34  17
 25  12  35  16  31  10

 
Example2:   A closed tour on a 18x12 chessboard

    SIZE 217 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "6K*6L"   >>>   K^L

    3  ENTER  2  R/S  >>>   18.012 = R00                                                      ---Execution time = 104s---

And you find in registers R01 thru R216
 
 

   2   93  100    7    4   91  104  195  202  109  106  193
  99    6    3   92  101    8  201  108  105  194  203  110
  86    1   94    5   90  213  188  103  196  107  192  207
  95   98   85  212    9  102  197  200  187  206  111  204
 216   87   96   11  214   89  210  189  198  113  208  191
  97   84  215   88  211   10  199  186  209  190  205  112
  22   77   12   27   24   75  124  179  114  129  126  177
  83   26   23   76   13   28  185  128  125  178  115  130
  70   21   78   25   74   17  172  123  180  127  176  119
  79   82   69   16   29   14  181  184  171  118  131  116
  20   71   80   31   18   73  122  173  182  133  120  175
  81   68   19   72   15   30  183  170  121  174  117  132
  42   61   32   47   44   59  144  163  134  149  146  161
  67   46   43   60   33   48  169  148  145  162  135  150
  54   41   62   45   58   37  156  143  164  147  160  139
  63   66   53   36   49   34  165  168  155  138  151  136
  40   55   64   51   38   57  142  157  166  153  140  159
  65   52   39   56   35   50  167  154  141  158  137  152

 
Note:

-When the program stops, M.NNN is stored in R00
 

    d)  6Kx7L Chessboards
 

-As above, a closed tour on a 6x7 chessboard is the basis.
-And several copies of this tour are connected to produce larger tours
 

Data Registers:          R00 = m.nnn

Flags:  SF 00 <-> the moves are successively displayed
            SF 01 <-> the moves are successively stored in data registers R01 thru Rm.n
            SF 02 <-> the moves are successively stored in the current data file ( size at least m.n+1 )

            SF 04 <-> no prompt

Subroutines:  "M1" "M2" ......  "M8"  "IN"
 
 

 01 LBL "6K*7L"
 02 6
 03 XROM "IN"
 04 3
 05 RCL 00
 06 -
 07 LBL 01
 08 XROM "M6"
 09 XROM "M4"
 10 XROM "M7"
 11 XROM "M2"
 12 XROM "M5"
 13 FS? 10
 14 GTO 00
 15 RCL M
 16 STO T
 17 RDN
 18 LBL 02
 19 XROM "M4"
 20 XROM "M5"
 21 XROM "M4"
 22 XROM "M7"
 23 XROM "M2"		  24 XROM "M5"
 25 DSE Z
 26 GTO 02
 27 LBL 00
 28 XROM "M7"
 29 RCL M
 30 STO T
 31 CLX
 32 RCL 00
 33 -
 34 2
 35 +
 36 DSE Y
 37 ISG Z
 38 ""  ;F0
 39 GTO 00
 40 LBL 03
 41 XROM "M1"
 42 XEQ 13
 43 LBL 00
 44 XROM "M8"
 45 XEQ 14
 46 DSE Z		  47 GTO 03
 48 DSE N
 49 GTO 01
 50 XROM "M1"
 51 RCL O
 52 STO N
 53 CLX
 54 RCL 00
 55 ST+ X
 56 +
 57 DSE Y
 58 ISG X
 59 LBL 04
 60 XROM "M2"
 61 XEQ 13
 62 XROM "M3"
 63 DSE N
 64 GTO 04
 65 GTO 09
 66 LBL 13
 67 XROM "M4"
 68 XROM "M7"
 69 XROM "M2"		  70 XROM "M4"
 71 XROM "M1"
 72 RTN
 73 LBL 14
 74 XROM "M6"
 75 XROM "M8"
 76 XROM "M1"
 77 XROM "M2"
 78 XROM "M3"
 79 XROM "M5"
 80 XROM "M3"
 81 XROM "M6"
 82 XROM "M7"
 83 XROM "M6"
 84 XROM "M1"
 85 XROM "M4"
 86 XROM "M7"
 87 XROM "M1"
 88 XROM "M8"
 89 XROM "M3"
 90 XROM "M3"
 91 XROM "M1"
 92 XROM "M4"		  93 XROM "M5"
 94 XROM "M6"
 95 XROM "M8"
 96 XROM "M1"
 97 XROM "M3"
 98 XROM "M1"
 99 XROM "M6"
100 XROM "M5"
101 XROM "M6"
102 XROM "M8"
103 RTN
104 LBL 09
105 RCL O
106 .007
107 *
108 RCL 00
109 +
110 STO 00
111 CLA
112 END

 
      ( 207 bytes / SIZE 001 or 1+6Kx7L )
 
 

      STACK        INPUTS      OUTPUTS
           Y            K             /
           X            L       M.NNN

 
Example1:   A closed tour on a 6x7 chessboard

   SIZE 043 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "6K*7L"   >>>   K^L

    1  ENTER   R/S  >>>   6.007 = R00                                                      ---Execution time = 23s---

And you find in registers R01 thru R42
 
 

 31  24  41  10  39  36  21
 42  11  32  29  22   9  38
 25  30  23  40  37  20  35
  4   1  12  33  28  17   8
 13  26   3   6  15  34  19
  2   5  14  27  18   7  16

 
Example2:   A closed tour on a 12x14 chessboard

    SIZE 169 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "6K*7L"   >>>   K^L

    2  ENTER  R/S  >>>   12.014 = R00                                                      ---Execution time = 84s---

And we find in registers R01 thru R168
 
 

  73   66  167   52  165  162   63  150  143  160  129  158  155  140
 168   53   74   71   64   51  164  161  130  151  148  141  128  157
  67   72   65  166  163   62   77  144  149  142  159  156  139  154
   4    1   54   75    70   59   50    81   78  131  152  147  136  127
  55   68    3   48   57   76   61  132  145   80  125  134  153  138
   2    5   56   69   60   49   58   79   82  133  146  137  126  135
  37   30   47   16   45   42   27  114  107  124   93  122  119  104
   6   17   38   35   28   15   44   83   94  115  112  105   92  121
  31   36   29   46   43   26   41  108  113  106  123  120  103  118
  10    7   18   39   34   23   14   87   84   95  116  111  100   91
  19   32    9   12   21   40   25   96  109   86   89   98  117  102
   8   11   20   33   24   13   22   85   88   97  110  101   90   99

 
Note:

-When the program stops, M.NNN is stored in R00
 

    e)  7Kx8L Chessboards
 

-A closed tour on a 7x8 chessboard is the basis.
-And several copies of this tour are connected to produce larger tours
 

Data Registers:          R00 = m.nnn

Flags:  SF 00 <-> the moves are successively displayed
            SF 01 <-> the moves are successively stored in data registers R01 thru Rm.n
            SF 02 <-> the moves are successively stored in the current data file ( size at least m.n+1 )

            SF 04 <-> no prompt

Subroutines:  "M1" "M2" ......  "M8"  "IN"
 
 

 01 LBL "7K*8L"
 02 7
 03 XROM "IN"
 04 4
 05 RCL 00
 06 ST+ X
 07 -
 08 LBL 01
 09 RCL M
 10 STO T
 11 RDN
 12 XROM "M7"
 13 XEQ 14
 14 XROM "M7"
 15 XEQ 13
 16 FS? 10
 17 GTO 09
 18 LBL 02
 19 XROM "M4"
 20 XEQ 13
 21 DSE Z
 22 GTO 02
 23 RCL M
 24 STO T
 25 RDN
 26 XROM "M3"
 27 XEQ 12		  28 XROM "M8"
 29 XEQ 11
 30 XROM "M4"
 31 XEQ 14
 32 LBL 03
 33 XROM "M8"
 34 LBL 09
 35 FS? 10
 36 XROM "M3"
 37 XEQ 12
 38 DSE Z
 39 X=0?
 40 GTO 00
 41 XROM "M8"
 42 XEQ 11
 43 XROM "M4"
 44 XEQ 14
 45 GTO 03
 46 LBL 00
 47 DSE N
 48 GTO 01
 49 XROM "M8"
 50 RCL O
 51 STO N
 52 CLX
 53 RCL 00
 54 ST+ X		  55 DSE X
 56 +
 57 DSE Y
 58 LBL 04
 59 XROM "M3"
 60 XEQ 11
 61 DSE N
 62 GTO 04
 63 GTO 09
 64 LBL 11
 65 XROM "M2"
 66 XROM "M3"
 67 XROM "M2"
 68 RTN
 69 LBL 12
 70 XROM "M2"
 71 XROM "M8"
 72 XROM "M1"
 73 XROM "M7"
 74 XROM "M6"
 75 XROM "M7"
 76 XROM "M5"
 77 XROM "M4"
 78 XROM "M5"
 79 XROM "M2"
 80 XROM "M3"
 81 XROM "M2"		  82 XROM "M1"
 83 XROM "M6"
 84 XROM "M4"
 85 XROM "M1"
 86 XROM "M8"
 87 XROM "M1"
 88 XROM "M6"
 89 XROM "M7"
 90 XROM "M4"
 91 XROM "M6"
 92 XROM "M8"
 93 XROM "M5"
 94 XROM "M4"
 95 XROM "M3"
 96 XROM "M1"
 97 XROM "M1"
 98 XROM "M6"
 99 XROM "M4"
100 XROM "M6"
101 XROM "M7"
102 XROM "M2"
103 XROM "M1"
104 XROM "M6"
105 RTN
106 LBL 13
107 XROM "M6"
108 XROM "M7"		 109 XROM "M4"
110 XROM "M5"
111 XROM "M4"
112 XROM "M2"
113 RTN
114 LBL 14
115 XROM "M5"
116 XROM "M4"
117 XROM "M7"
118 XROM "M8"
119 XROM "M7"
120 XROM "M4"
121 XROM "M2"
122 XROM "M1"
123 RTN
124 LBL 09
125 RCL O
126 125
127 /
128 RCL 00
129 +
130 STO 00
131 CLA
132 END

 
      ( 253 bytes / SIZE 001 or 1+7Kx8L )
 
 

      STACK        INPUTS      OUTPUTS
           Y            K             /
           X            L       M.NNN

 
Example1:   A closed tour on a 7x8 chessboard

   SIZE 057 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "7K*8L"   >>>   K^L

    1  ENTER   R/S  >>>   7.008 = R00                                                      ---Execution time = 28s---

And you find in registers R01 thru R56
 
 

 35  56  21  10  37  54  23  12
 20   9  36  55  22  11  40  53
  1  34  45  38  51   6  13  24
 30  19   8   5  46  39  52  41
 33   2  31  44   7  50  25  14
 18  29   4  47  16  27  42  49
  3  32  17  28  43  48  15  26

 
Example2:   A closed tour on a 14x16 chessboard

    SIZE 225 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "7K*8L"   >>>   K^L

    2  ENTER  R/S  >>>   14.016 = R00                                                      ---Execution time = 109s---

And we find in registers R01 thru R224
 
 

  91  224   77   10   93  222   79   12  199  220  185  118  201  218  187  120
  76    9   92  223   78   11   96  221  184  117  200  219  186  119  204  217
   1   90  101   94  107    6   13   80  109  198  209  202  215  114  121  188
  86   75    8    5  102   95  108   97  194  183  116  113  210  203  216  205
  89    2   87  100    7  106   81   14  197  110  195  208  115  214  189  122
  74   85    4  103   16   83   98  105  182  193  112  211  124  191  206  213
   3   88   73   84   99  104   15   82  111  196  181  192  207  212  123  190
  42   63   28   17   44   61   30   19  150  171  136  125  152  169  138  127
  27   72   43   62   29   18   47   60  135  180  151  170  137  126  155  168
  64   41   52   45   58   69   20   31  172  149  160  153  166  177  128  139
  37   26   71   68   53   46   59   48  145  134  179  176  161  154  167  156
  40   65   38   51   70   57   32   21  148  173  146  159  178  165  140  129
  25   36   67   54   23   34   49   56  133  144  175  162  131  142  157  164
  66   39   24   35   50   55   22   33  174  147  132  143  158  163  130  141

 
Note:

-When the program stops, M.NNN is stored in R00
 

    f)  7Kx10L Chessboards
 

-A closed tour on a 7x10 chessboard is the basis.
-And several copies of this tour are connected to produce larger tours
 

Data Registers:          R00 = m.nnn

Flags:  SF 00 <-> the moves are successively displayed
            SF 01 <-> the moves are successively stored in data registers R01 thru Rm.n
            SF 02 <-> the moves are successively stored in the current data file ( size at least m.n+1 )

            SF 04 <-> no prompt

Subroutines:  "M1" "M2" ......  "M8"  "IN"
 
 

 01 LBL "7K*10L"
 02 7
 03 XROM "IN"
 04 3
 05 RCL 00
 06 -
 07 LBL 01
 08 RCL M
 09 STO T
 10 RDN
 11 XROM "M6"  
 12 XEQ 14
 13 XROM "M3"
 14 XEQ 13
 15 FS? 10
 16 GTO 09
 17 LBL 02
 18 XROM "M4"
 19 XEQ 13
 20 DSE Z
 21 GTO 02
 22 RCL M
 23 STO T
 24 RDN
 25 XROM "M7"
 26 XEQ 12
 27 XROM "M1"
 28 XEQ 11
 29 XROM "M5"		  30 XEQ 14
 31 LBL 03
 32 XROM "M8"
 33 LBL 09
 34 FS? 10
 35 XROM "M7"
 36 XEQ 12
 37 DSE Z
 38 X=0?
 39 GTO 00
 40 XROM "M1"  
 41 XEQ 11
 42 XROM "M5"
 43 XEQ 14
 44 GTO 03
 45 LBL 00
 46 DSE N
 47 GTO 01
 48 XROM "M1"
 49 RCL O
 50 STO N
 51 CLX
 52 RCL 00
 53 ST+ X
 54 +
 55 DSE Y
 56 ISG X
 57 LBL 04
 58 XROM "M2"		  59 XEQ 11
 60 DSE N
 61 GTO 04
 62 GTO 09
 63 LBL 11
 64 XROM "M3"  
 65 XROM "M2"
 66 XROM "M3"
 67 XROM "M2"
 68 XROM "M5"
 69 XROM "M8"
 70 XROM "M3"
 71 RTN
 72 LBL 12
 73 XROM "M6"
 74 XROM "M8"
 75 XROM "M3"
 76 XROM "M6"
 77 XROM "M1"
 78 XROM "M8"
 79 RTN
 80 LBL 13
 81 XROM "M2"
 82 XROM "M4"
 83 XROM "M5"
 84 XROM "M4"
 85 XROM "M7"
 86 XROM "M6"
 87 RTN		  88 LBL 14
 89 XROM "M7"
 90 XROM "M2"
 91 XROM "M4"
 92 XROM "M7"
 93 XROM "M5"  
 94 XROM "M7"
 95 XROM "M1"
 96 XROM "M4"
 97 XROM "M5"
 98 XROM "M3"
 99 XROM "M2"
100 XROM "M7"
101 XROM "M4"
102 XROM "M1"
103 XROM "M7"
104 XROM "M4"
105 XROM "M6"
106 XROM "M8"
107 XROM "M8"
108 XROM "M8"
109 XROM "M5"
110 XROM "M4"
111 XROM "M4"
112 XROM "M2"
113 XROM "M8"
114 XROM "M7"
115 XROM "M5"
116 XROM "M7"		 117 XROM "M1"
118 XROM "M4"
119 XROM "M5"
120 XROM "M3"
121 XROM "M1"
122 XROM "M1"
123 XROM "M1"  
124 XROM "M6"
125 XROM "M5"
126 XROM "M4"
127 XROM "M6"
128 XROM "M7"
129 XROM "M1"
130 XROM "M8"
131 XROM "M2"
132 XROM "M5"
133 XROM "M8"
134 XROM "M3"
135 XROM "M2"
136 RTN
137 LBL 09
138 RCL O
139  E2
140 /
141 RCL 00
142 +
143 STO 00
144 CLA
145 END

 
    ( 280 bytes / SIZE 001 or 1+7Kx10L )
 
 

      STACK        INPUTS      OUTPUTS
           Y            K             /
           X            L       M.NNN

 
Example1:   A closed tour on a 7x10 chessboard

   SIZE 071 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "7K*10L"   >>>   K^L

    1  ENTER   R/S  >>>   7.010 = R00                                                      ---Execution time = 35s---

And you find in registers R01 thru R70
 
 

 67  50  69  36  65  48  21  44  63  46
 70    3  66  49   8  37  64  47  30  43
 51  68   5   2  35  20  27  22  45  62
  4   1  16   9  26   7  38  31  42  29
 15  52  13   6  19  34  23  28  61  58
 12  17  54  25  10  39  56  59  32  41
 53  14  11  18  55  24  33  40  57  60

 
Example2:   A closed tour on a 7x20 chessboard

    SIZE 141 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "7K*10L"   >>>   K^L

    1  ENTER  2  R/S  >>>   7.020 = R00                                                      ---Execution time = 68s---

And we find in registers R01 thru R140
 
 

 137   50  139   36  135   48   21   44  133   46  129  112  131   98  127  110   83  106  125  108
 140    3  136   49    8   37  134   47   30   43  132   65  128  111   70   99  126  109   92  105
  51  138    5    2   35   20   27   22   45   62  113  130   67   64   97   82   89   84  107  124
   4    1   16    9   26    7   38   31   42   29   66   63   78   71   88   69  100   93  104   91
  15   52   13    6   19   34   23   28   61   58   77  114   75   68   81   96   85   90  123  120
  12   17   54   25   10   39   56   59   32   41   74   79  116   87   72  101  118  121   94  103
  53   14   11   18   55   24   33   40   57   60  115   76   73   80  117   86   95  102  119  122

 
Note:

-When the program stops, M.NNN is stored in R00
 

    g)  8Kx5L Chessboards
 

-A closed tour on a 8x5 chessboard is the basis.
-And several copies of this tour are connected to produce larger tours
 

Data Registers:          R00 = m.nnn

Flags:  SF 00 <-> the moves are successively displayed
            SF 01 <-> the moves are successively stored in data registers R01 thru Rm.n
            SF 02 <-> the moves are successively stored in the current data file ( size at least m.n+1 )

            SF 04 <-> no prompt

Subroutines:  "M1" "M2" ......  "M8"  "IN"
 
 

 01 LBL "8K*5L"
 02 8
 03 XROM "IN"
 04 4
 05 RCL 00
 06 -
 07 LBL 01
 08 RCL M
 09 STO T
 10 RDN
 11 XROM "M6"
 12 XEQ 14
 13 XROM "M3"
 14 XROM "M5"
 15 XROM "M4"
 16 XROM "M5"
 17 FS? 10
 18 GTO 09
 19 LBL 02
 20 XROM "M4"
 21 XROM "M5"
 22 XROM "M4"
 23 XROM "M5"		  24 DSE Z
 25 GTO 02
 26 RCL M
 27 STO T
 28 RDN
 29 XROM "M7"
 30 XEQ 13
 31 XROM "M1"
 32 XEQ 12
 33 XROM "M5"
 34 XEQ 14
 35 LBL 03
 36 XROM "M8"
 37 LBL 09
 38 FS? 10
 39 XROM "M7"
 40 XEQ 13
 41 DSE Z
 42 X=0?
 43 GTO 00
 44 XROM "M1"
 45 XEQ 12
 46 XROM "M5"		  47 XEQ 14
 48 GTO 03
 49 LBL 00
 50 DSE N
 51 GTO 01
 52 XROM "M1"
 53 RCL O
 54 STO N
 55 CLX
 56 RCL 00
 57 ST+ X
 58 +
 59 DSE Y
 60 ISG X
 61 LBL 04
 62 XROM "M2"
 63 XEQ 12
 64 DSE N
 65 GTO 04
 66 GTO 09
 67 LBL 12
 68 XROM "M4"
 69 XROM "M7"		  70 XROM "M1"
 71 XROM "M3"
 72 XROM "M4"
 73 XROM "M7"
 74 XROM "M1"
 75 XROM "M4"
 76 RTN
 77 LBL 13
 78 XROM "M8"
 79 XROM "M1"
 80 XROM "M8"
 81 XROM "M3"
 82 XROM "M2"
 83 XROM "M5"
 84 XROM "M5"
 85 XROM "M7"
 86 RTN
 87 LBL 14
 88 XROM "M6"
 89 XROM "M5"
 90 XROM "M2"
 91 XROM "M3"
 92 XROM "M8"		  93 XROM "M7"
 94 XROM "M5"
 95 XROM "M3"
 96 XROM "M2"
 97 XROM "M7"
 98 XROM "M2"
 99 XROM "M5"
100 XROM "M6"
101 XROM "M8"
102 XROM "M1"
103 XROM "M8"
104 XROM "M2"
105 RTN
106 LBL 09
107 RCL O
108 200
109 /
110 RCL 00
111 +
112 STO 00
113 CLA
114 END

 
     ( 217 bytes / SIZE 001 or 1+8Kx5L )
 
 

      STACK        INPUTS      OUTPUTS
           Y            K             /
           X            L       M.NNN

 
Example1:   A closed tour on a 8x5 chessboard

   SIZE 041 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "8K*5L"   >>>   K^L

    1  ENTER   R/S  >>>   8.005 = R00                                                      ---Execution time = 21s---

And you find in registers R01 thru R40
 
 

 28  39  18  35  26
 19  36  27  32  17
 40  29  38  25  34
 37  20  33  16  31
 12   1  30   7  24
 21   6  11   2  15
 10  13   4  23   8
  5  22   9  14   3

 
Example2:   A closed tour on a 8x10 chessboard

    SIZE 081 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "8K*5L"   >>>   K^L

    1  ENTER  2  R/S  >>>   8.010 = R00                                                      ---Execution time = 40s---

And we find in registers R01 thru R80
 
 

 28  79  18  75  26  59  70  49  66  57
 19  76  27  72  17  50  67  58  63  48
 80  29  78  25  74  71  60  69  56  65
 77  20  73  16  31  68  51  64  47  62
 12   1  30   7  24  43  32  61  38  55
 21   6  11   2  15  52  37  42  33  46
 10  13   4  23   8  41  44  35  54  39
  5  22   9  14   3  36  53  40  45  34

 
Note:

-When the program stops, M.NNN is stored in R00
 

    h)  8Kx8L Chessboards
 

-A closed tour on a 8x8 chessboard is the basis.
-And several copies of this tour are connected to produce larger tours
 

Data Registers:          R00 = m.nnn

Flags:  SF 00 <-> the moves are successively displayed
            SF 01 <-> the moves are successively stored in data registers R01 thru Rm.n
            SF 02 <-> the moves are successively stored in the current data file ( size at least m.n+1 )

            SF 04 <-> no prompt

Subroutines:  "M1" "M2" ......  "M8"  "IN"
 
 

 01 LBL "8K*8L"
 02 8
 03 XROM "IN"
 04 4
 05 RCL 00
 06 -
 07 LBL 01
 08 RCL M
 09 STO T
 10 RDN
 11 XROM "M6"
 12 XROM "M4"
 13 FS? 10
 14 GTO 09
 15 LBL 02
 16 XROM "M5"
 17 XROM "M4"
 18 XROM "M5"
 19 XROM "M4"
 20 DSE Z
 21 GTO 02
 22 RCL M		  23 STO T
 24 RDN
 25 XROM "M6"
 26 XEQ 14
 27 XROM "M1"
 28 XEQ 13
 29 LBL 03
 30 XROM "M1"
 31 LBL 09
 32 FS? 10
 33 XROM "M6"
 34 XEQ 14
 35 DSE Z
 36 X=0?
 37 GTO 00
 38 XROM "M1"
 39 XEQ 13
 40 GTO 03
 41 LBL 00
 42 DSE N
 43 GTO 01
 44 XROM "M1"		  45 RCL O
 46 STO N
 47 CLX
 48 RCL 00
 49 ST+ X
 50 +
 51 DSE Y
 52 ISG X
 53 LBL 04
 54 XROM "M2"
 55 XEQ 13
 56 XROM "M2"
 57 XROM "M4"
 58 DSE N
 59 GTO 04
 60 GTO 09
 61 LBL 13
 62 XROM "M2"
 63 XROM "M3"
 64 XROM "M2"
 65 XROM "M5"
 66 XROM "M6"		  67 XROM "M5"
 68 XROM "M2"
 69 XROM "M4"
 70 XROM "M6"
 71 XROM "M1"
 72 XROM "M2"
 73 XROM "M7"
 74 XROM "M6"
 75 XROM "M8"
 76 XROM "M5"
 77 XROM "M2"
 78 XROM "M4"
 79 XROM "M7"
 80 XROM "M8"
 81 XROM "M8"
 82 XROM "M3"
 83 XROM "M3"
 84 XROM "M6"
 85 XROM "M7"
 86 XROM "M1"
 87 XROM "M3"
 88 XROM "M2"		  89 XROM "M3"
 90 XROM "M6"
 91 XROM "M5"
 92 XROM "M2"
 93 XROM "M4"
 94 XROM "M5"
 95 XROM "M7"
 96 XROM "M6"
 97 XROM "M7"
 98 XROM "M2"
 99 XROM "M7"
100 XROM "M4"
101 XROM "M3"
102 XROM "M2"
103 XROM "M3"
104 XROM "M8"
105 XROM "M1"
106 XROM "M8"
107 XROM "M7"
108 XROM "M5"
109 XROM "M6"
110 XROM "M8"		 111 XROM "M2"
112 XROM "M3"
113 RTN
114 LBL 14
115 XROM "M7"
116 XROM "M6"
117 XROM "M8"
118 XROM "M3"
119 XROM "M6"
120 XROM "M1"
121 XROM "M8"
122 RTN
123 LBL 09
124 RCL O
125 125
126 /
127 RCL 00
128 +
129 STO 00
130 CLA
131 END

 
     ( 251 bytes /SIZE 001 or 1+8Kx8L )
 
 

      STACK        INPUTS      OUTPUTS
           Y            K             /
           X            L       M.NNN

 
Example1:   A closed tour on a 8x8 chessboard

   SIZE 065 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "8K*8L"   >>>   K^L

    1  ENTER   R/S  >>>   8.008 = R00                                                      ---Execution time = 32s---

And you find in registers R01 thru R64
 
 

 14  63  38  57  12  61  36  31
 39  56  13  62  37  32  11  60
 64  15  40  33  58  25  30  35
 55  42  23  16  27  34  59  10
 22   1  18  41  24  29  26  49
 43  54  21  28  17  48   9   6
  2  19  52  45   4   7  50  47
 53  44   3  20  51  46   5   8

 
Example2:   A closed tour on a 16x16 chessboard

    SIZE 257 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "8K*5L"   >>>   K^L

    2  ENTER  R/S  >>>   16.016 = R00                                                      ---Execution time = 123s---

And we find in registers R01 thru R256
 
 

 206  255  230  249  204  253  228  223  152  201  176  195  150  199  174  169
 231  248  205  254  229  224  203  252  177  194  151  200  175  170  149  198
 256  207  232  225  250  217  222  227  202  153  178  171  196  163  168  173
 247  234  215  208  219  226  251   74  193  180  161  154  165  172  197  148
 214    1   210  233  216  221  218  241  160   75  156  179  162  167  164  187
 235  246  213  220  209  240   73   70  181  192  159  166  155  186  147  144
   2  211  244  237   68   71  242  239   76  157  190  183  142  145  188  185
 245  236   67  212  243  238   69   72  191  182  141  158  189  184  143  146
  18    3   42   61   16   65   40   35   92   77  116  135   90  139  114  109
  43   60   17   66   41   36   15   64  117  134   91  140  115  110   89  138
   4   19   44   37   62   29   34   39   78   93  118  111  136  103  108  113
  59   46   27   20   31   38   63   14  133  120  101   94  105  112  137   88
  26    5   22   45   28   39   30   53  100   79   96  119  102  107  104  127
  47   58   25   32   21   52   13   10  121  132   99  106   95  126   87   84
   6   23   56   49    8   11   54   51   80   97  130  123   82   85  128  125
  57   48    7   24   55   50    9   12  131  122   81   98  129  124   83   86

 
Note:

-When the program stops, M.NNN is stored in R00
 

    i)  10x3L Chessboards
 

-As usual, a closed tour on a 10x3 chessboard is the basis ( with the 5x6 chessboard, it's the smallest case where a closed tour exists ).
-And several copies of this tour are connected to produce larger tours
-Here, however, we cannot connect these chessboards in the same way.
-So, all the larger chessboards have 10 rows.
 

Data Registers:         R00 = m.nnn

Flags:  SF 00 <-> the moves are successively displayed
            SF 01 <-> the moves are successively stored in data registers R01 thru Rm.n
            SF 02 <-> the moves are successively stored in the current data file ( size at least m.n+1 )

            SF 04 <-> no prompt

Subroutines:  "M1" "M2" ......  "M8"
 
 

 01 LBL "10*3L"
 02 " L=?"
 03 FC? 04
 04 PROMPT
 05 STO M
 06 STO N
 07 STO O
 08 10
 09 STO 00
 10 CLX
 11 FS? 02		  12 SEEKPT
 13 2
 14 RCL 00
 15 ST+ X
 16 -
 17 LBL 01
 18 XROM "M6"
 19 XROM "M8"
 20 XROM "M5"
 21 XROM "M2"
 22 XROM "M7"		  23 XROM "M4"
 24 XROM "M1"
 25 XROM "M6"
 26 XROM "M4"
 27 XROM "M4"
 28 XROM "M7"
 29 XROM "M4"
 30 XROM "M4"
 31 XROM "M6"
 32 XROM "M1"
 33 XROM "M4"		  34 XROM "M7"
 35 XROM "M2"
 36 XROM "M5"
 37 XROM "M8"
 38 XROM "M1"
 39 XROM "M1"
 40 XROM "M8"
 41 DSE M
 42 GTO 01
 43 XROM "M5"
 44 RCL 00		  45 ST+ X
 46 +
 47 DSE Y
 48 ISG X
 49 LBL 02
 50 XROM "M2"
 51 XROM "M3"
 52 XROM "M6"
 53 XROM "M3"
 54 XROM "M5"
 55 XROM "M8"		  56 XROM "M1"
 57 DSE N
 58 GTO 02
 59 RCL O
 60 .003
 61 *
 62 RCL 00
 63 +
 64 STO 00
 65 CLA
 66 END

 
       ( 130 bytes / SIZE 001 or 1+10x3L )
 
 

      STACK        INPUT      OUTPUT
           X            L       M.NNN

 
Example1:   A closed tour on a 10x3 chessboard

   SIZE 031 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "10*3L"   >>>   L=?

    1   R/S  >>>   10.003 = R00                                                      ---Execution time = 16s---

And you find in registers R01 thru R30
 
 

  7   2   5
  4  23   8
  1   6   3
 22   9  24
 25  30  11
 10  21  26
 27  12  29
 18  15  20
 13  28  17
 16  19  14

 
Example2:   A closed tour on a 10x9 chessboard

    SIZE 091 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "10*3L"   >>>   L=?

    3  R/S  >>>   10.009 = R00                                                      ---Execution time = 45s---

And we find in registers R01 thru R90
 
 

  7   2   5  30  25  28  53  48  51
  4  23   8  27  46  31  50  69  54
  1   6   3  24  29  26  47  52  49
 22   9  84  45  32  77  68  55  70
 85  90  11  78  83  34  71  76  57
 10  21  86  33  44  79  56  67  72
 87  12  89  80  35  82  73  58  75
 18  15  20  41  38  43  64  61  66
 13  88  17  36  81  40  59  74  63
 16  19  14  39  42  37  62  65  60

 
Note:

-When the program stops, M.NNN is stored in R00
 

    j)  12x3L Chessboards
 

-A closed tour on a 12x3 chessboard is the basis.
-And several copies of this tour are connected to produce larger tours
-Here, however, we cannot connect these chessboards in the same way.
-So, all the larger chessboards also have 12 rows.
 

Data Registers:         R00 = m.nnn

Flags:  SF 00 <-> the moves are successively displayed
            SF 01 <-> the moves are successively stored in data registers R01 thru Rm.n
            SF 02 <-> the moves are successively stored in the current data file ( size at least m.n+1 )

            SF 04 <-> no prompt

Subroutines:  "M1" "M2" ......  "M8"
 
 

 01 LBL "12*3L"
 02 " L=?"
 03 FC? 04
 04 PROMPT
 05 STO M
 06 STO N
 07 STO O
 08 CLX
 09 FS? 02
 10 SEEKPT
 11 12
 12 STO 00
 13 CHS
 14 LBL 01		  15 XROM "M7"
 16 XROM "M6"
 17 XROM "M1"
 18 XROM "M4"
 19 XROM "M7"
 20 XROM "M2"
 21 XROM "M5"
 22 DSE M
 23 GTO 01
 24 XROM "M8"
 25 RCL 00
 26 ST+ X
 27 +
 28 DSE Y		  29 DSE X
 30 LBL 02
 31 XROM "M3"
 32 XROM "M1"
 33 XROM "M1"
 34 XROM "M6"
 35 XROM "M3"
 36 XROM "M6"
 37 XROM "M4"
 38 XROM "M1"
 39 XROM "M7"
 40 XROM "M1"
 41 XROM "M8"
 42 XROM "M1"		  43 XROM "M4"
 44 XROM "M6"
 45 XROM "M4"
 46 XROM "M1"
 47 XROM "M6"
 48 XROM "M1"
 49 XROM "M1"
 50 XROM "M7"
 51 XROM "M4"
 52 XROM "M1"
 53 XROM "M6"
 54 XROM "M3"
 55 XROM "M8"
 56 XROM "M5"		  57 XROM "M4"
 58 XROM "M4"
 59 XROM "M5"
 60 DSE N
 61 GTO 02
 62 RCL O
 63 .003
 64 *
 65 RCL 00
 66 +
 67 STO 00
 68 CLA
 69 END

 
           ( 138 bytes / SIZE 001 or 1+12x3L )
 
 

      STACK        INPUT      OUTPUT
           X            L       M.NNN

 
Example1:   A closed tour on a 12x3 chessboard

   SIZE 037 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "12*3L"   >>>   L=?

    1   R/S  >>>   12.003 = R00                                                      ---Execution time = 18s---

And you find in registers R01 thru R36
 
 

 29  32  27
 26  19  30
 31  28  33
 20  25  18
 23  34  21
 10  17  24
 35  22  11
 12   9  16
 15  36  13
  6   3   8
  1  14   5
  4   7   2

 
Example2:   A closed tour on a 12x9 chessboard

    SIZE 109 or greater

   CF 00  SF 01  CF 02   CF 04  XEQ "12*3L"   >>>   L=?

    3  R/S  >>>   12.009 = R00                                                      ---Execution time = 53s---

And we find in registers R01 thru R108
 
 

 101  104   99   72   75   70   43   46   41
  98   91  102   69   62   73   40   33   44
 103  100  105   74   71   76   45   42   47
  92   97   90   63   68   61   34   39   32
  95  106   93   66   77   64   37   48   35
  82   89   96   53   60   67   24   31   38
 107   94   83   78   65   54   49   36   25
  84   81   88   55   52   59   26   23   30
  87  108   85   58   79   56   29   50   27
   6    3   80   13   10   51   20   17   22
   1   86    5    8   57   12   15   28   19
   4    7    2   11   14    9   18   21   16

 
Note:

-When the program stops, M.NNN is stored in R00
 

3°)  A Test: Do we Get a Tour ?
 

-After storing the m.n positions of a knight on a mxn chessboard, you might wish to check if it's really a tour

0-Clear flag 02  CF 02
1-Store m.nnn  in R00
2-Store the positions in R01 thru Rmn
3-XEQ "KNT?"

>>>  With an 8x8 chessboard, the execution time is about 130 seconds if CF 02

-Your HP-41 will answer "NO TOUR" or "OPEN TOUR" or "CLOSED TOUR"

-You may also create a DATA file with a size m.n+1 at leat ( the 1st register - 000 - is unused in the data file ). In this case

0-Set flag 02  SF 02
1-Store m.nnn  in R00
2-Store the positions in the DATA file
3-XEQ "KNT?"

>>>  With an 8x8 chessboard, the execution time is about 158 seconds if SF 02

-The X-Functions  SEEKPT & SAVEX  are slower than  STO IND --
 
 

Data Registers:           •  R00 = m.nnn               ( Registers R00 - and R01 thru Rmn if CF 02 - are to be initialized before executing "KNT?" )

                                      •  R01 ............... •  Rmxn = positions of the knight IF  flag F02 is clear

Flags:   F02-F10             CF 02 if the positions of the knight are stored in data registers R01 thru Rmn
                                         SF 02 ----------------------------------------- a data file in extended memory
Subroutines: /
 

-Lines 27-35-107-121-135-152-170-178 are three-byte GTO's
 
 

 01  LBL "KNT?"
 02  SF 10
 03  RCL 00
 04  FRC
 05   E3
 06  *
 07  RCL 00
 08  INT
 09  STO Q
 10  *
 11  STO N
 12  ENTER
 13  SIGN
 14  FS? 02
 15  SEEKPT
 16  STO P
 17  LBL 14
 18  FC? 02 
 19  RCL IND Y     
 20  FS? 02
 21  GETX
 22  X=Y?
 23  GTO 10
 24  RDN
 25  DSE Y
 26  GTO 14
 27  GTO 11
 28  LBL 13
 29  CF 10		  30  SIGN
 31  STO P
 32  GTO 01
 33  LBL 10
 34  FC? 10
 35  GTO 12
 36  FC? 02
 37  X<> Z
 38  FS? 02
 39  RCLPT
 40  FS? 02
 41  DSE X
 42  STO O
 43  RCL Q
 44  MOD
 45  STO M
 46  ISG P
 47  LBL 01
 48  RCL M            
 49  ENTER
 50  SIGN
 51  X=Y?
 52  GTO 03
 53  ST+ X
 54  X=Y?
 55  GTO 02
 56  RCL O
 57  RCL Q
 58  -		  59  X<>Y
 60  -
 61  X<=0?
 62  GTO 02
 63  XEQ 01
 64  X=Y?
 65  GTO 10
 66  LBL 02
 67  RCL O
 68  RCL Q
 69  ST+ X
 70  -
 71  PI
 72  SIGN
 73  -
 74  X<=0?
 75  GTO 03           
 76  XEQ 01
 77  X=Y?
 78  GTO 10
 79  LBL 03
 80  RCL M
 81  X=0?
 82  GTO 07
 83  RCL O
 84  RCL Q
 85  ST+ X
 86  DSE X
 87  -		  88  X<=0?
 89  GTO 04
 90  XEQ 01
 91  X=Y?
 92  GTO 10
 93  LBL 04
 94  RCL M
 95  RCL Q
 96  DSE X
 97  X=Y?
 98  GTO 06
 99  RCL O
100  X<>Y
101  DSE X
102  -
103  X<=0?
104  GTO 05          
105  XEQ 01
106  X=Y?
107  GTO 10
108  LBL 05
109  RCL N
110  RCL O
111  RCL Q
112  +
113  ENTER
114  SIGN
115  ST+ X
116  +		 117  X>Y?
118  GTO 06
119  XEQ 01
120  X=Y?
121  GTO 10
122  LBL 06
123  RCL N
124  RCL O
125  RCL Q
126  ST+ X
127  +
128  ENTER
129  SIGN
130  +
131  X>Y?
132  GTO 07
133  XEQ 01          
134  X=Y?
135  GTO 10
136  LBL 07
137  RCL M
138  ENTER
139  SIGN
140  X=Y?
141  GTO 09
142  RCL N
143  RCL O
144  RCL Q
145  ST+ X		 146  +
147  DSE X
148  X>Y?
149  GTO 08
150  XEQ 01
151  X=Y?
152  GTO 10
153  LBL 08
154  RCL M
155  ENTER
156  SIGN
157  ST+ X
158  X=Y?
159  GTO 09          
160  RCL N
161  RCL O
162  RCL Q
163  +
164  R^
165  -
166  X>Y?
167  GTO 09
168  XEQ 01
169  X=Y?
170  GTO 10
171  LBL 09
172  FC? 10
173  GTO 09
174  RCL N		 175  RCL P
176  DSE X
177  X=Y?
178  GTO 13
179  LBL 11
180  "NO TOUR"
181  GTO 00
182  LBL 01
183  FS? 02
184  SEEKPT
185  FS? 02
186  GETX
187  FC? 02
188  RCL IND X
189  RCL P
190  RTN
191  LBL 12
192  "CLOSED
TOUR"
193  GTO 00
194  LBL 09
195  "OPEN TOUR"
196  LBL 00
197  AVIEW
198  CF 10
199  END

 
        ( 363 bytes / SIZE 001 or 1+MxN )
 
 

      STACK        INPUT      OUTPUT
           X             /             /

 
Note:

-Synthetic registers P & Q are used, so don't interrupt "KNT?", it would modify these registers.
 

4°)  Concatenation of 2 Closed Tours
 

"KT+CKT" tries to concatenate 2 closed tours, provided they have the same number of rows

-Store the m x n1 tour in registers R01 ..... Rm.n1  and the m x n2 tour in registers R1+m.n1
-Then XEQ "KT+CKT"

-The calculator will display "FAILED" if it couldn't merge the 2 tours.

-The HP41 seeks for patterns like this ( and other similar configurations ):

   LEFT    RIGHT

      4  *    *  *             4  *  *  *
      *  *    8  *             *  *  5  *
      *  5    *  *             *  b  *  *      with b = a + 1
      *  *    *  7             *  *  *  a

      BEFORE               AFTER
 
 

Data Registers:          R00 = m.nnn  with  m > 4  &  n = n1 + n2

                                     R01 to Rmn = the resulting closed tour.

Flags:      F06-F07-F08                 SF 04 <-> no prompt
Subroutines: /

-Line 139 is a three-byte GTO
 
 

 01 LBL "KT+CKT"
 02  " M^N1^N2?"
 03  FC? 04
 04  PROMPT
 05  STO O
 06  RDN
 07  STO N
 08  2
 09  -
 10  X<>Y
 11  STO 00
 12  *
 13  3
 14  +
 15  LBL 01
 16  2
 17  -
 18  STO M
 19  RCL 00
 20  ST+ X
 21  +
 22  1
 23  +
 24  RCL X
 25  RCL 00
 26  +
 27  2
 28  +
 29  RCL Y
 30  RCL 00
 31  -		  32  1
 33  +
 34  RCL IND Z     
 35  STO Q
 36  RCL IND Z
 37  ST- Q
 38  RCL IND M
 39  ST- Q
 40  RCL IND T
 41  ST+ Q
 42  SF 07
 43  GTO 14
 44  LBL 13
 45  RCL M
 46  FC?C 07
 47  GTO 11
 48  3
 49  ST+ M
 50  RCL 00
 51  *
 52  +
 53  STO Y
 54  RCL 00
 55  -
 56  2
 57  +
 58  RCL X
 59  RCL 00
 60  -
 61  DSE X
 62  RCL IND Z		  63  STO Q
 64  RCL IND Z
 65  ST- Q
 66  RCL IND Z     
 67  ST- Q
 68  RCL IND M
 69  ST+ Q
 70  GTO 14
 71  LBL 11
 72  RCL N
 73  RCL 00
 74  ST* Y
 75  -
 76  X<>Y
 77  X<Y?
 78  GTO 01
 79  "FAILED"
 80  PROMPT
 81  LBL 14
 82  CF 06
 83  X>Y?
 84  SF 06
 85  X>Y?
 86  X<>Y
 87  STO P
 88  -
 89  ENTER
 90  SIGN
 91  -
 92  X=0?
 93  GTO 00		  94  LASTX
 95  ST+ X
 96  +
 97  RCL 00
 98  SIGN
 99  CLX
100  RCL N
101  ST* L
102  X<> L
103  -
104  X#0?
105  GTO 13         
106  X<> L
107  STO P
108  FS? 06
109  CHS
110  ST+ Q
111  LBL 00
112  RDN
113  CF 08
114  X>Y?
115  SF 08
116  X<Y?
117  X<>Y
118  ENTER
119  X<> M
120  X<> Z
121  -
122  ENTER
123  SIGN
124  -		 125  X=0?
126  GTO 00
127  LASTX
128  STO M
129  ST+ X
130  +
131  RCL 00
132  RCL O
133  *
134  -
135  X=0?
136  GTO 14          
137  R^
138  STO M
139  GTO 13
140  LBL 14
141  X<> L
142  FS? 08
143  CHS
144  ST- Q
145  LBL 00
146  RCL 00
147  RCL N
148  *
149  STO Y
150  PI
151  INT
152  10^X
153  /
154  +
155  RCL 00		 156  RCL O
157  *
158  +
159  CF 07
160  RCL Q
161  X=0?
162  SF 07
163  LBL 10
164  CLX
165  RCL IND Y   
166  RCL M
167  -
168  FC? 07
169  ISG X
170  ""
171  FS? 07
172  CHS
173  X>0?
174  GTO 10
175  RCL 00
176  RCL O
177  *
178  +
179  LBL 10
180  RCL P
181  +
182  STO IND Y
183  DSE Y
184  GTO 10
185  X<>Y
186  INT		 187  LBL 12
188  RCL P
189  RCL IND Y
190  X<=Y?
191  GTO 12
192  X<>Y
193  CLX
194  RCL 00
195  RCL O
196  *
197  +
198  STO IND Z    
199  LBL 12
200  X<> Z
201  DSE X
202  GTO 12
203  RCL N
204  RCL O
205  +
206   E3
207  /
208  RCL 00
209  +
210  STO 00
211  CLA
212  END

 
     ( 330 bytes )
 
 

      STACK        INPUTS      OUTPUTS
           Z         M > 4             /
           Y            N1             /
           X            N2       M.NNN

   With  M > 4  &  N = N1 + N2

Example1:  You want to create a 8 x 13 closed tour. This may be done by merging an 8x8 tour & an 8x5 tour:

-Load for instance the following routine in main memory:
 
 

 01  LBL "?"
 02  SF 01
 03  SF 04
 04  1
 05  ENTER^
 06  XROM "8K*5L"
 07  1.065040
 08  REGMOVE
 09  1
 10  ENTER^
 11  XROM "8K*8L"
 12  8
 13  ENTER^
 14  ENTER^
 15  5
 16  XROM "KT+CKT"
 17  END

 
  SIZE 105  at least  and  XEQ "?"  >>>>    8.013                  ---Execution time = 92s---

 And you get in registers R01 thru R104 the following tour:
 
 

  14  103   78   97   12  101   76   31   44   55   74   51   42
  79   96   13  102   77   32   11  100   75   52   43   48   73
 104   15   80   33   98   25   30   35   56   45   54   41   50
  95   82   23   16   27   34   99   10   53   36   49   72   47
  22    1   18   81   24   29   26   89   68   57   46   63   40
  83   94   21   28   17   88    9    6   37   62   67   58   71
   2   19   92   85    4    7   90   87   66   69   60   39   64
  93   84    3   20   91   86    5    8   61   38   65   70   59

 
Example2:  You want to create a 5 x 14 closed tour. This may be done by merging an 5x6 tour & an 5x8 tour:

-There is no 5x8 tour in this page but there is an 8x5 tour, so we can use "TRNT"
-Load for instance the following routine in main memory:
 
 

 01  LBL "?"
 02  SF 01
 03  SF 04
 04  1
 05  ENTER^
 06  XROM "8K*5L"
 07  41
 08  XROM "TRNT"
 09  41.031040
 10  REGMOVE
 11  1
 12  ENTER^
 13  XROM "5K*6L"
 14  5
 15  ENTER^
 16  6
 17  ENTER^
 18  8
 19  XROM "KT+CKT"
 20  END

 
 ( lines 07 to 10 are necessary because with "TRNT", the blocks of registers cannot overlap
   so 31  XROM "TRNT" would give wrong results )

  SIZE 071  at least  and  XEQ "?"  >>>>    5.014                  ---Execution time = 82s---

 And you get in registers R01 thru R70 the following closed tour:
 
 

 53  70  59  48  55  68  37  46  25  28  13  44  15  20
 60  49  54  69  64  47  26  29  36  45  24  19  12  43
  1  52   3  58  67  56   7  38  27  32  35  14  21  16
  4  61  50  65   6  63  30  33  40   9  18  23  42  11
 51   2   5  62  57  66  39   8  31  34  41  10  17  22

 
Notes:

-"KT+CKT" may also be used to merge an open tour ( on the left ) and a closed tour ( on the right ) to try to produce a larger open tour.
-When the program stops, M.NNN is stored in R00.
-Synthetic registers P & Q are used, so don't interrupt "KT+CKT", these registers would be modified.
 

5°)  Transpose of an MxN Tour
 

-"TRNT" creates an NxM tour from a MxN tour
-It takes m.nnn in R00 and another address L > M.N in X-register and stores the matrix transpose in RLL  RLL+1 ......
 
 

Data Registers:            •  R00 = m.nnn                              ( Registers R00 thru Rmn are to be initialized before executing "TRNT" )

                                       •  R01 .....   •  Rmn = MxN tour

 >>> When the program stops,    RLL ...................... RLL+mn-1 = "transposed" tour

Flags:  /
Subroutines:  /
 
 

 01  LBL "TRNT"
 02  RCL 00
 03  FRC
 04   E3
 05  *
 06  STO O
 07   E5
 08  /		  09  +
 10  STO Y
 11  RCL 00      
 12  INT
 13  STO M
 14  STO N
 15  SIGN
 16  LBL 10		  17  RCL IND X
 18  STO IND T
 19  CLX
 20  SIGN
 21  +
 22  ISG Z
 23  ""
 24  DSE M		  25  GTO 10      
 26  X<>Y
 27  RCL N
 28  STO M
 29  SIGN
 30  +
 31  STO Z
 32  X<>Y		  33  DSE O
 34  GTO 10      
 35  RDN
 36  DSE X
 37  ""
 38  INT
 39  CLA
 40  END

 
     ( 66 bytes )
 
 

      STACK        INPUT      OUTPUT
           X            L          L

 
Example:    Let's take the knight's tour

        R01   R04   R07   R10                   1   4   7  10
        R02   R05   R08   R11       =          8  11  2   5
        R03   R06   R09   R12                   3   6   9  12
 
 

  1   4   7  10
  8  11   2   5
  3   6   9  12

 
-Store  3.004  in  R00   and if you want to get the transpose in R13 .....

  13  XEQ "TRNT"  >>>>    13                     ---Execution time = 5s---

-And we have in R13 thru R24
 
 

  1   8   3
  4  11   6
  7   2   9
 10   5  12

 
Note:

-The blocks of registers cannot overlap.
 

6°)  Displaying the results
 

-If flag F02 is clear, "VWKT" simply displays successively the numbers in a block of registers specified by a control number  bbb.eee
  where Rbb is the 1st register & Ree is the last register of the block

-It may also be used to display the contents of a data file in X-memory: in this case, set flag F02
-The data file must be the current file.

-Line 14 is append =
 
 

 01  LBL "VWKT"
 02  SIGN
 03  FS? 02
 04  SEEKPT
 05  LBL 12
 06  " R"		  07  RCL d
 08  FIX 00          
 09  CF 29
 10  ARCL Y
 11  STO d
 12  CLX		  13  X<>Y
 14  >"="
 15  FC? 02
 16  ARCL IND L
 17  FS? 02
 18  GETX		  19  FS? 02
 20  ARCL X       
 21  FS? 02
 22  RDN
 23  ISG X
 24  CLX		  25  AVIEW         
 26  FC? 21
 27  PSE
 28  ISG L
 29  GTO 12
 30  END

 
     ( 61 bytes )
 
 

      STACK        INPUT      OUTPUT
           X        bbb.eee            /

 
Example:   To display registers R13 to R24

   CF 02

   13.024  XEQ "VWKT"  >>>   R13 = ...
                                                   R14 = ...

                                                   R24 = ...

Note:

-If flag F21 is clear, the HP41 executes a pause ( PSE ) between each AVIEW
 
 

Remark:

-These programs will create knight's tours on chessboards of various sizes but of course not all the chessboards.
-You will find many other methods - very clever - in references [3] and [4]
 

References:

[1]  http://mathworld.wolfram.com/KnightsTour.html
[2]  Closed (Re-entrant) Knight Tours - www.BordersChess.org/KTclosed.htm
[3]  Ian Parberry - An efficient algorithm for the Knight’s tour problem - Discrete Applied Mathematics 73 (1997) 251-260
[4]  Shun-Shii Lina, Chung-LiangWeib - Optimal algorithms for constructing knight’s tours on arbitrary n×m chessboards -
       Discrete Applied Mathematics 146 (2005) 219 – 232