(20S) N-queens

[arhtur]

I didn't see a posting for this before, so I thought I would try implementing the N-queens algorithm (as previously posted by Xerxes) on the HP 20s. This is particularly difficult since thee are only 99 program steps and the 20s doesn't have indexed addressing of memory registers. To overcome this, I use a single register and use each digit to represent a storage register (therefore, this should work for a board size up to 9). Retrieving a digit is not too difficult. Changing a digit is more difficult - the easiest way I found was to provide the set digit algorithm with the original value, subtracting it, and then adding the new value (times the correct power of 10, of course).

Because program memory is limited, you must do CLRG first, and then store the board size in register 4 (a size of 4 runs in a reasonable amount of time, if you do 8, it takes much longer (around 10 minutes or so)).

To run the program, call XEQ A

After the program finishes running, RCL 0

For a board size of 4, the result is 24130 (least significant digit is not used, therefore the queen positions are 2, 4, 1, 3). For a board size of 8, the result is 5, 7, 2, 6, 3, 1, 4, 8.

Program listing is attached as a .PDF file.

[Felix Stehli]

Very nice! The nQueens benchmark is a favourite of mine and I implemented it on a variety of devices and in a lot of different programming languages. Doing it on a machine with such limited capabilities is quite a challenge.

What is the running time for finding the first solution to the 8-queens problem?

[arhtur]

On my HP 20s, for 8 queens, it took about 9 minutes and 53 seconds.

[Dave Britten]

I was trying to do this on my 65 a while back, since it too has no indirect addressing, and a similar amount of storage registers and program steps. The imprecise log/antilog made things a bit cumbersome, and I wasn't able to fit the whole algorithm into memory. Perhaps I should revisit it sometime.

[Thomas Klemm]

(06-22-2021 02:18 PM)Dave Britten Wrote:  Perhaps I should revisit it sometime.

Cf. (HP-65) N-Queens