(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