+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: HP-65/67/97 Software Library (/forum-12.html)
+--- Thread: (HP-65) N-Queens (/thread-17910.html)
(HP-65) N-Queens - Dave Britten - 01-09-2022 07:45 PM
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 13Flowcharts from Mathematical Recreations for the Programmable Calculator, on which this program is based:
Main Program Flowchart
Attack Checking Procedure Flowchart
RE: (HP-65) N-Queens - Nihotte(lma) - 01-13-2022 05:50 PM
(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
RE: (HP-65) N-Queens - Dave Britten - 01-13-2022 10:49 PM
(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...
RE: (HP-65) N-Queens - Thomas Klemm - 03-02-2022 01:21 AM
(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
RE: (HP-65) N-Queens - Dave Britten - 06-25-2023 01:43 PM
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
RE: (HP-65) N-Queens - Steve Simpkin - 06-25-2023 05:54 PM
(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.
RE: (HP-65) N-Queens - Steve Simpkin - 06-26-2023 05:47 AM
(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."