(25) N-Queens

[Thomas Klemm]

References

• (HP-65) N-Queens
  

The program is based on the flowcharts that are linked in Dave Britten's solution.
But I had to make some changes:

• the number format is \(0.a_1 a_2 \cdots a_8\)
• the indexes \(m_0\) and \(m_1\) are decremented so we can use comparison with \(0\)
• the number \(10\) is kept as a constant in register \(m_6\)
• storage arithmetic helped to save some steps
  

Registers

0: # of old queens
1: New queen
2: Old queens
3: Chopping block
4: i counter
5: n size of board
6: 10 as constant


Initialization and Run

CLEAR REG
FIX 8
8
STO 0
STO 5
10
STO 6
GTO 13
R/S


Solution

After about 40 minutes this result is shown:

0.57263148

This corresponds to the following setup:

    5 7 2 6 3 1 4 8
8: | | | | | | | |#|
7: | |#| | | | | | |
6: | | | |#| | | | |
5: |#| | | | | | | |
4: | | | | | | |#| |
3: | | | | |#| | | |
2: | | |#| | | | | |
1: | | | | | |#| | |

The next solutions will be shown after starting the program again with R/S.
However for now it will not detect the end.
There simply was no memory left to do so.

Program

The program can be used in this HP-25C emulator.

Code:

01: 24 01    : RCL 1
02: 23 51 02 : STO + 2
03: 24 06    : RCL 6
04: 23 71 02 : STO / 2
05: 01       : 1
06: 23 41 00 : STO - 0
07: 24 00    : RCL 0
08: 15 61    : g x<>0
09: 13 13    : GTO 13
10: 24 02    : RCL 2
11: 74       : R/S
12: 13 36    : GTO 36
13: 24 05    : RCL 5
14: 23 01    : STO 1
15: 24 02    : RCL 2
16: 23 03    : STO 3
17: 34       : CLx
18: 23 04    : STO 4
19: 01       : 1
20: 23 51 04 : STO + 4
21: 24 06    : RCL 6
22: 23 61 03 : STO * 3
23: 24 03    : RCL 3
24: 15 71    : g x=0
25: 13 01    : GTO 01
26: 14 01    : f INT
27: 23 41 03 : STO - 3
28: 24 01    : RCL 1
29: 14 71    : f x=y
30: 13 36    : GTO 36
31: 41       : -
32: 15 03    : g ABS
33: 24 04    : RCL 4
34: 14 61    : f x<>y
35: 13 19    : GTO 19
36: 01       : 1
37: 23 41 01 : STO - 1
38: 24 01    : RCL 1
39: 15 61    : g x<>0
40: 13 15    : GTO 15
41: 01       : 1
42: 23 51 00 : STO + 0
43: 24 06    : RCL 6
44: 23 61 02 : STO * 2
45: 24 02    : RCL 2
46: 14 01    : f INT
47: 23 41 02 : STO - 2
48: 23 01    : STO 1
49: 13 36    : GTO 36

[Dave Britten]

Wow, impressive! I took a very brief stab at doing this, but I was about 20 steps over the limit, with no obvious way to trim any more fat.

[Stefan Falk]

This is really freaking cool. I've done N Queens on each and every calculator and computer (from the HP 9820 in school on) I had under my fingers (not yet on the HP Prime), and am just working on it on my "new" 48GX. I read that it has been done on the HP-65, which is fantastic enough. But on the HP-25 - amazing, unbelievable! Chapeau!

Best Regards,
Stefan

[Thomas Klemm]

(08-03-2023 12:44 PM)Stefan Falk Wrote:  I've done N Queens on each and every calculator (…) I had under my fingers …

You might also like a this solution: N-queens benchmark and the HP-17BII
Both are listed in the Calculator Speed Benchmark using the N-Queens Problem.

Here's my solution for the HP-25 in the thread: Weakest calculator/pocket computer that can do Tower of Hanoi?
It shows how much can be done despite the limitations.