(PC-1200) N-Queens
02-21-2023, 09:16 PM (This post was last modified: 03-16-2023 02:42 PM by robve.)
Post: #1
 robve Senior Member Posts: 398 Joined: Sep 2020
(PC-1200) N-Queens
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
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

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.

"I count on old friends" -- HP 71B,Prime|Ti VOY200,Nspire CXII CAS|Casio fx-CG50...|Sharp PC-G850,E500,2500,1500,14xx,13xx,12xx...
02-22-2023, 06:39 AM
Post: #2
 xerxes Member Posts: 157 Joined: Jun 2014
RE: (PC-1200) N-Queens
Pretty fast for it's time. Nice to have it in the list now. Thanks for your effort.

Calculator Benchmark
02-22-2023, 01:19 PM
Post: #3
 Dave Britten Senior Member Posts: 2,250 Joined: Dec 2013
RE: (PC-1200) N-Queens
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.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)