(HP-65) N-Queens

[Dave Britten]

For a long time, I wasn't sure N-Queens with up to an 8x8 board was possible on the HP 65, owing to the lack of indirect addressing. I was reading Mathematical Recreations for the Programmable Calculator (by Dean Hoffman and Lee Mohler, Hayden Book Company 1982) this morning, and found a chapter discussing the problem. They have flowcharts of a relatively simple algorithm that doesn't require a calculator with indirect addressing. I'm not clever enough to have come up with it on my own, but I'm clever enough to shoehorn it into the HP 65's 100 steps of program memory.

To use: load the program, press f REG, enter n into stack register X (so 8 for an 8x8 board), and press A to start searching. With an 8x8 board, the program will run for about 50 minutes and stop with the first solution in the display, in the format of 8 digits showing the column number of the queen in each row. You can press R/S to continue searching for the next solution. When all solutions have been found, the program will stop with 0 in the display.

Note that this program abuses subroutines, treating them as one-step GTO instructions to save space. There are no RTNs, and the program pointers will be a little goofy after completion of the program, so you may need to press RTN or reload the program if you want to run it again with a different board size.

Code:

STO 5   33 05
LBL     23
B       12
RCL 5   34 05
RCL 7   34 07
g x=y   35 23
GTO     22
6       06
1       01
STO 1   33 01
LBL     23
E       15
RCL 2   34 02
0       00
LBL     23
D       14
1       01
+       61
g x><y  35 07
1       01
0       00
STO 8   33 08
/       81
0       00
g x=y   35 23
GTO     22
3       03
g RDown 35 08
ENTER   41
f-1     32
INT     83
-       51
g x><y  35 07
g LSTx  35 00
RCL 8   34 08
*       71
RCL 1   34 01
g x=y   35 23
GTO     22
C       13
-       51
g       35
ABS     06
g x=y   35 23
GTO     22
C       13
g RDown 35 08
D       14
LBL     23
3       03
RCL 2   34 02
RCL 8   34 08
*       71
RCL 1   34 01
+       61
STO 2   33 02
1       01
STO     33
+       61
7       07
B       12
LBL     23
6       06
RCL 2   34 02
R/S     84
LBL     23
C       13
RCL 5   34 05
RCL 1   34 01
g x=y   35 23
GTO     22
5       05
1       01
+       61
STO 1   33 01
E       15
LBL     23
5       05
RCL 7   34 07
1       01
-       51
STO 7   33 07
0       00
g x>y   35 24
CLx     44
R/S     84
RCL 2   34 02
RCL 8   34 08
/       81
ENTER   41
f-1     32
INT     83
-       51
STO 2   33 02
g LSTx  35 00
RCL 8   34 08
*       71
STO 1   33 01
C       13

Flowcharts from Mathematical Recreations for the Programmable Calculator, on which this program is based:

Main Program Flowchart

Attack Checking Procedure Flowchart

[Nihotte(lma)]

(01-09-2022 07:45 PM)Dave Britten Wrote:  For a long time, I wasn't sure N-Queens with up to an 8x8 board was possible on the HP 65, owing to the lack of indirect addressing. ... I'm clever enough to shoehorn it into the HP 65's 100 steps of program memory.

Thanks to you Dave Britten !
I like this sort of challenge !

Have a happy new year and keep you safe !

Laurent

[Dave Britten]

(01-13-2022 05:50 PM)Nihotte(lma) Wrote:  

(01-09-2022 07:45 PM)Dave Britten Wrote:  For a long time, I wasn't sure N-Queens with up to an 8x8 board was possible on the HP 65, owing to the lack of indirect addressing. ... I'm clever enough to shoehorn it into the HP 65's 100 steps of program memory.

Thanks to you Dave Britten !
I like this sort of challenge !

Have a happy new year and keep you safe !

Laurent

Thanks Laurent, you as well! I've been thinking over whether I can cram this onto the HP 25, but it's not coming to me so far. If anybody can manage that, I'll be really impressed...

[Thomas Klemm]

(01-13-2022 10:49 PM)Dave Britten Wrote:  I've been thinking over whether I can cram this onto the HP 25, but it's not coming to me so far. If anybody can manage that, I'll be really impressed...

Cf. (25) N-Queens

Cheers
Thomas

[Dave Britten]

I see that Eric now has a scan of "Mathematical Recreations for the Programmable Calculator" available on literature.hpcalc.org if anybody cares to see this and all the other problems in full:

https://literature.hpcalc.org/items/1664

[Steve Simpkin]

(06-25-2023 01:43 PM)Dave Britten Wrote:  I see that Eric now has a scan of "Mathematical Recreations for the Programmable Calculator" available on literature.hpcalc.org if anybody cares to see this and all the other problems in full:

https://literature.hpcalc.org/items/1664

Thanks Dave
I used my HP-25 (still works great) for almost 10 years as my only calculator before moving to newer HP models so this book helps rekindle some very fond memories.

I am amazed that you were able to fit the 8x8 N-Queens into the HP-65 and am in awe that Thomas was able to fit it into the HP-25. Unbelievable.

[Steve Simpkin]

(06-25-2023 01:43 PM)Dave Britten Wrote:  I see that Eric now has a scan of "Mathematical Recreations for the Programmable Calculator" available on literature.hpcalc.org if anybody cares to see this and all the other problems in full:

https://literature.hpcalc.org/items/1664

I'm enjoying the book so far. This sentence early on was entertaining...

"We wish to thank Texas Instruments for giving us two TI-57s free of charge and Hewlett Packard for lending us an HP33E without a charger."