(PC-1200) N-Queens

[robve]

The Sharp PC-1200/PC-1201 was made 1977-1978
10+2 digits precision, 14 digit VFD
2 standard registers (x and y operands)
1 constant register (constant operations with = key)
3 stat registers (internal n, ∑x, ∑x²)
4 bracket registers (parenthesized calculations)
12 memory registers (M0 to M9, s and t)
1 label register, set with GTO n to run a routine with S/E and cleared with CA
128 steps keystroke-programmable
Links:
http://www.rskey.org/CMS/index.php/exhibit-hall/96
http://www.arithmomuseum.com/album.php?c...ang=en&t=5
https://www.johnwolff.id.au/calculators/...PC1201.htm
http://le-rayon-des-calculatrices.fr/WordPress3/?p=2787
https://www.hpmuseum.org/forum/thread-2503.html

N-Queens algorithm references

The program is based on the flowcharts that are linked in Dave Britten's solution for the HP-65.

Registers

s = the specified board size n
t = 0 constant for testing
M0 = number of old queens placed
M1 = new queen
M2 = old queens placed
M3 = chopping block
M4 = counter

Execution

Press CA to run the program from the start. Enter n, for example enter 8 to run the 8-queens benchmark, then press S/E

Solution

In 12 minutes and 42 seconds the display shows the first solution u  15863724.



where u means user input (the HLT operation). Pressing S/E calculates the next solution, and so on, until the calculator returns -1 without requesting further user input.

The running time for all solutions of the 8-queens problem should be about 4 hours, which is rough estimation based on running all solutions on the Sharp PC-G850 using the same "chopping block" algorithm (in BASIC) and by using the time of the first solution to scale. It turns out that the Sharp PC-1200 is only 10 times slower than the PC-G850 BASIC for this same algorithm (the PC-G850 Z80 CPU runs at 8MHz.) The PC-1200 is a fast keystroke programmable, especially for the 70s.

Program

The 94-step keystroke program with steps and comments (key codes are omitted for clarity).

Code:

000     CAM     ; clear all memory
001     x→M s   ; n -> s
        
        ; main loop
        
002     LBL 0   ;
003     RM 0    ;
004     -       ;
005     RM s    ;
006     =       ;
007     x=t 4   ; if M0=s then found a solution
008     1       ;
009     x→M 1   ; 1 -> M1
        
        ; does the new queen attack an old?
        
010     LBL 1   ;
011     RM 2    ;
012     x→M 3   ; M2 -> M3
013     0       ;
014     x→M 4   ; 0 -> M4
        
        ; check attack loop
        
015     LBL 2   ;
016     1       ;
017     M+ 4    ; M4+1 -> M4
018     RM 3    ;
019     x=t 3   ; if M3=0 then new queen does not attack old
020     ÷       ;
021     1       ;
022     0       ;
023     =       ;
024     x→M 3   ; M3/10 -> M3
025     frac    ; frac(M3) -> x
026     +/-     ;
027     M+ 3    ; M3-frac(M3) -> M3
028     +/-     ;
029     ×       ;
030     1       ;
031     0       ;
032     -       ;
033     RM 1    ;
034     =       ; 10*x-M1 -> x
035     x=t 5   ; if x=0 then new queen attacks an old
036     -       ;
037     RM 4    ;
038     =       ; x-M4 -> x
039     x=t 5   ; if x=0 then new queen attacks an old
040     +       ;
041     RM 4    ;
042     =       ;
043     =       ; x+M4+M4 -> x
044     x=t 5   ; if x=0 then new queen attacks an old
045     GTO 2   ; repeat check attack loop
        
        ; new queen does not attack any old
        
046     LBL 3   ;
047     RM 2    ;
048     ×       ;
049     1       ;
050     0       ;
051     +       ;
052     RM 1    ;
053     =       ;
054     x→M 2   ; 10*M2+M1 -> M2
055     1       ;
056     M+ 0    ; M0+1 -> M0
057     GTO 0   ; repeat main loop
        
        ; found a solution
        
058     LBL 4   ;
059     RM 2    ;
060     HLT     ; display M2 and wait on S/E key press
        
        ; continue searching (new queen attacks an old)
        
061     LBL 5   ;
062     RM 1    ;
063     -       ;
064     RM s    ;
065     =       ;
066     x=t 6   ; if M1=s then next
067     1       ;
068     M+ 1    ; M1+1 -> M1
069     GTO 1   ; does the new queen attack an old?
        
        ; next
        
070     LBL 6   ;
071     1       ;
072     +/-     ;
073     M+ 0    ; M0-1 -> M0
074     RM 0    ;
075     x<0 7   ; if M0<0 then stop
076     RM 2    ;
077     ÷       ;
078     1       ;
079     0       ;
080     =       ;
081     x→M 2   ; M2/10 -> M2
082     frac    ; frac(M2) -> x
083     +/-     ;
084     M+ 2    ; M2-frac(M2) -> M2
085     +/-     ;
086     ×       ;
087     1       ;
088     0       ;
089     =       ;
090     x→M 1   ; 10*x -> M1
091     GTO 5   ; continue searching
        
        ; stop
        
092     LBL 7   ;
093     S/E     ; end

The program with key codes is listed below. The PC-1200/PC-1201 lists key codes, which are entered by pressing a key or key combination. The machine produces a satisfying beep to acknowledge the key entry (did I mention I love this calculator?) Key codes can be edited, inserted (INS) and deleted (DEL) in a program while moving forward or backward a step with FST and BST, respectively (pressing GTO + digit before switching to PRO mode jumps directly to a label). Two-digit key codes are simply the ROWCOL location of a key on the keyboard. For example, 84 (row 8, column 4) is the = key and F-12 is the (shifted, hence F) HLT key. Digits are 00 to 09. Some codes have an operand, such as F-13-05 for (shifted) LBL 5.

Code:

000     F-45    CAM     ; clear all memory
001     55-82   x→M s   ; n -> s
        
        ; main loop
        
002     F-13-00 LBL 0   ;
003     65-00   RM 0    ;
004     64      -       ;
005     65-82   RM s    ;
006     84      =       ;
007     F-75-04 x=t 4   ; if M0=s then found a solution
008     01      1       ;
009     55-01   x→M 1   ; 1 -> M1
        
        ; does the new queen attack an old?
        
010     F-13-01 LBL 1   ;
011     65-02   RM 2    ;
012     55-03   x→M 3   ; M2 -> M3
013     00      0       ;
014     55-04   x→M 4   ; 0 -> M4
        
        ; check attack loop
        
015     F-13-02 LBL 2   ;
016     01      1       ;
017     75-04   M+ 4    ; M4+1 -> M4
018     65-03   RM 3    ;
019     F-75-03 x=t 3   ; if M3=0 then new queen does not attack old
020     44      ÷       ;
021     01      1       ;
022     00      0       ;
023     84      =       ;
024     55-03   x→M 3   ; M3/10 -> M3
025     F-83    frac    ; frac(M3) -> x
026     82      +/-     ;
027     75-03   M+ 3    ; M3-frac(M3) -> M3
028     82      +/-     ;
029     54      ×       ;
030     01      1       ;
031     00      0       ;
032     64      -       ;
033     65-01   RM 1    ;
034     84      =       ; 10*x-M1 -> x
035     F-75-05 x=t 5   ; if x=0 then new queen attacks an old
036     64      -       ;
037     65-04   RM 4    ;
038     84      =       ; x-M4 -> x
039     F-75-05 x=t 5   ; if x=0 then new queen attacks an old
040     74      +       ;
041     65-04   RM 4    ;
042     84      =       ;
043     84      =       ; x+M4+M4 -> x
044     F-75-05 x=t 5   ; if x=0 then new queen attacks an old
045     14-02   GTO 2   ; repeat check attack loop
        
        ; new queen does not attack any old
        
046     F-13-03 LBL 3   ;
047     65-02   RM 2    ;
048     54      ×       ;
049     01      1       ;
050     00      0       ;
051     74      +       ;
052     65-01   RM 1    ;
053     84      =       ;
054     55-02   x→M 2   ; 10*M2+M1 -> M2
055     01      1       ;
056     75-00   M+ 0    ; M0+1 -> M0
057     14-00   GTO 0   ; repeat main loop
        
        ; found a solution
        
058     F-13-04 LBL 4   ;
059     65-02   RM 2    ;
060     F-12    HLT     ; display M2 and wait on S/E key press
        
        ; continue searching (new queen attacks an old)
        
061     F-13-05 LBL 5   ;
062     65-01   RM 1    ;
063     64      -       ;
064     65-82   RM s    ;
065     84      =       ;
066     F-75-06 x=t 6   ; if M1=s then next
067     01      1       ;
068     75-01   M+ 1    ; M1+1 -> M1
069     14-01   GTO 1   ; does the new queen attack an old?
        
        ; next
        
070     F-13-06 LBL 6   ;
071     01      1       ;
072     82      +/-     ;
073     75-00   M+ 0    ; M0-1 -> M0
074     65-00   RM 0    ;
075     F-65-07 x<0 7   ; if M0<0 then stop
076     65-02   RM 2    ;
077     44      ÷       ;
078     01      1       ;
079     00      0       ;
080     84      =       ;
081     55-02   x→M 2   ; M2/10 -> M2
082     F-83    frac    ; frac(M2) -> x
083     82      +/-     ;
084     75-02   M+ 2    ; M2-frac(M2) -> M2
085     82      +/-     ;
086     54      ×       ;
087     01      1       ;
088     00      0       ;
089     84      =       ;
090     55-01   x→M 1   ; 10*x -> M1
091     14-05   GTO 5   ; continue searching
        
        ; stop
        
092     F-13-07 LBL 7   ;
093     85      S/E     ; end

- Rob

Edit: minor edit to name the "chopping block" algorithm plus program with key codes included; added FST/BST and GTO navigation comment.

[xerxes]

Pretty fast for it's time. Nice to have it in the list now. Thanks for your effort.

[Dave Britten]

Very cool! I'm glad I stumbled across this algorithm in Mathematical Recreations. It's opened up solutions to the problem on a lot of "weaker" hardware. Hats off to Dean Hoffman and Lee Mohler for devising it.

I've tried finding a PC-1200 or PC-1201 on ebay a few times, but they're too rich for my blood.