(15C/15C Limited Edition) Knight's Tour

[Archilog]

Knight's Tour is an old problem of the graph theory in which it is required to move a knight on all the squares of a chess board without ever going through the same square again. Here is how Leonhard Euler presents his thoughts on this subject (in French) : http://eulerarchive.maa.org/docs/originals/E309.pdf

How can I play it?

It's better to have a chessboard and a good calculator like the HP-15C - or a really much faster HP-15C Limited Edition.

How does it work?

The heuristic used to find some solutions on a HP-15C is the one of the genius Herr Warnsdorf who discovered in 1823 an infallible way to go through all the squares of the chessboard without loss of time (as we say in chess, that is to say without loss of moves) by always choosing a square with a lower jump potential value among those legally available. Each square of the chessboard is for this purpose defined by its initial value as described in the following diagram :

Code:


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

The program is complete: once you have entered it into the machine, press the input abscissa (x), then [ENTER], then the ordinate (y) and finally [GSB] [A]. The program first displays the coordinates of this first square and the number of the move (for example : 1.2______01) ; a press on [R/S] starts and will continue the movement of the knight.

Here is the code:



Step 001-038: Initialization

Once the coordinates have been entered, pressing [A] formats the display, then clears all registers; this is followed by storing the initial coordinates and then filling registers 1 to 8 in decimal form less than 1 (the whole part will be used in routine 9); finally, register 0 is initialized with its upper limit in decimal part.


Step 039-142: Main loop and displacement calculation

Here we manage the display and the movement of the knight (the register I is used in this first case to count the number of the movement on the chessboard): if the number of the movement reaches 64, we stop with the Return (step 57).
Step 58 sees a second LBL B appear (an old habit now to reuse the previous program labels inherited from the HP-29C, just a jump to resume the move if square 64 is still not reached).
The work that then begins is to set the value of the square where the knight is located to zero: we therefore place the current coordinates in registers I (y, or row) and x (x, or column), then we call routines 9 (separation of row I into three parts for the stack: x : Integer value; y: 1st part and z: 2nd part, both in decimals less than 1) and 8 (assembly of the whole line) with the value of the square where the jumper between the two routines is set to zero. The whole part of the register indexed by I allows to temporarily retain the isolated decimal place.

Once the line has been modified and saved (step 63), the flags are initialized, an operation necessary at the beginning of the program and at each turn of loop B; flags 0 and 3 represent the obverse and reverse sides of the same medal because arming one requires disarming the other; they make it possible to choose with which register this operation will be carried out :

Code:

(R9 or R10) (+ or -) 1 ---> R11 or R12
└─────────┘└─────────┘     └─────────┘
   F0&F3        F1            F0&F3

(R10 or R9) (+ or -) 2 ---> R12 or R11
└─────────┘└─────────┘     └─────────┘
   F0&F3        F2            F0&F3

Flags 1 and 2 allow the choice of addition or subtraction of the integers 1 and 2 necessary for the movement of the knight. This way of proceeding requires a rigorous change of flag states which is managed by register I which sends the cursor to the successive labels 7 to 1, the eighth ((2^3)-th) state being the current one (yellow part of the code).

During the operation, the exit tests of the chessboard are carried out (steps 78, 82, 95 and 99) and send if necessary to the next square (whose value must be tested) by means of a jump for the same label 0 forward.


Step 143-174: Comparison

When a square makes a good candidate, you must compare its content (which will be reduced by one since, due to the presence of the knight within its range, it loses its potential that much) with the previous lowest value - or place its value in the comparison register if it is the first in the cycle of eight squares to be checked. This big maneuver is performed by routine C (in light green) which in turn calls routines 9 and 8 for isolation and assembly using register I again, reason for the exchanges R12<->R I. It is also necessary to check if the values of the boxes are not null (step 149), if the box is not the first one (step 158) and finally if it is interesting because it is of lesser value than the previous one registered (step 160): it is then routine E which takes care of keeping the value and the coordinates of the selected box (steps 163-169). As long as the eight flag states have not been modified, it means that the cycle around the knight has not been completed and that it is necessary to start again.

The cursor finally returns to step 106, we place the new coordinates (registers 13 and 14) as official coordinates (registers 9 and 10), without forgetting to empty register 15 (initial value of the cycle equal to zero) at step 114. And here we go again for one turn.

MEM 17 13 35-03 ; 29 Two-byte instructions ; 354 bytes (213+29+(16x7))

This program has been published for the first time on Silicium's forum.