(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.

[Archilog]

This heavy program is a good test to compare the original HP-15C and the Limited Edition speeds.

I suppressed the [R/S] (step 52) to measure the total time for the knight to walk through the 64 squares.

HP-15C Vintage: 63 moves in 57 minutes and 02 seconds (perhaps with one second of latency);
HP-15C Ltd. Ed.: 63 moves in 21 seconds and 69 100th.

Well, here the Limited Edition is 157 times faster than her old sister.

[Gene]

This is consistent with what has been seen.

The addition loop test [ LBL 01 + GTO 01 ] is 170X faster.

Calculating the constant e to 208 places is 125X faster.

All depends on what instructions are involved.

Good test here!

[Valentin Albillo]

(10-15-2020 09:33 PM)Gene Wrote:  This is consistent with what has been seen. [...] Calculating the constant e to 208 places is 125X faster.

You can find the 64-step HP-15C program that calculates e (=2.718..) to up to 208 decimal places in page 3 of my 6-page PDF article:

Long Live the HP-15C

V.

[Archilog]

I owe to the truth that C.Ret has designed a better code for the HP-15C than mine, both much shorter and much faster. The only consolation I have is to know that his brilliant attempt was inspired by mine, which was quite laborious - but the first step counts, right?
Here it is, with his permission.



You will find the flowchart and some explanations in French there.

On the 15C Limited Edition, the chessboard run lasts just under 12 seconds 9 tenths.
I will edit this message for the result of the vintage 15C: it is still calculating.

EDIT: On the vintage HP-15C, Knight's Tour is completed in less than 33 minutes 06 seconds 79 hundredth.
So the ratio in this program is 164,33 (Limited Edition version is 164 times faster than vintage version).

[rprosperi]

(10-21-2020 08:34 PM)Archilog Wrote:  EDIT: On the vintage HP-15C, Knight's Tour is completed in less than 33 minutes 06 seconds 79 hundredth.

33 Mins and 6.79 Seconds? How are you getting results that precise? Since the 15C doesn't have a built-in timer, it must be done by hand, so I'd say you really shouldn't report anything more precise than full seconds as your reaction time to see results and push buttons surely can't be more precise than that, right?

[Dave Frederickson]

(10-22-2020 01:22 AM)rprosperi Wrote:  33 Mins and 6.79 Seconds? How are you getting results that precise?

The dubious precision is likely the result of calculating the average of a number of runs and not rounding properly.

[Archilog]

Really?
Gentlemen, did I write this, precisely?

[Archilog]

Here's the explanation: I timed all the calculations with my HP-41CX.

For the original HP-15C, which has a very long calculation time, I performed the measurement three times: the first to estimate the necessary time, the second to make a correct measurement and the third for the final measurement.

Naturally, the time given here is the upper limit: it is not an equality, but an inequality (the time is less than...). I therefore published the maximum precision that I could measure, without taking into account the time needed to stop the stopwatch, but by judging that the calculation time was necessarily (and precisely) inferior to the measurement.