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