WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution

[iceman]

Greetings Xerxes!

Thank-you so much for monitoring this discussion and incorporating the findings into your excellent benchmark article.

May I respectfully recommend that the new BITMAP based N-Queens benchmark for WP-34S also be included in article 700, along with the most remarkable test result of 2.1 seconds on F/W version 3.3?

As you can determine from the attached photo, this benchmark developed by forum member Patrice correctly yields the Queen's positions in registers 4, 6, 8, 10, 12, 14, 16 and 18. This benchmark uses the WP-34S Binary operations commands (a-la HP-16C) and so represents a second legitimate example of the WP-34S N-Queens benchmark against the HP-16C. The original method is still relevant of course when comparing calculators that do not support bit functions, so I recommend including both in your article.

Here is the code for Patrice Torchet's BITMAP version:

Code:

WP-34S BITMAP Based N-Queens  (Patrice Torchet)
140    [f] LBL C        
141    TICKS        
142    STO K        
143    [f] BASE 16        
144    WSIZE 32        
145    [h] CLx        
146    STO C    //loop counter    
147    STO I    //Stack pointer    
148    1        
149    0        
150    1        
151    0        
152    1        
153    0        
154    1        
155    STO A    //0x1010101    
156    8        
157    STO B    //remaining Q    
158    [h] MASKR 08        
159    [h] SL 01        
160    STO 00    //0x1FE    
            
161    [f] LBL 02    //x=bitmap y=Q position    
162    INC C        
163    [h] BS?->Y    //test Q position    
164    [h] GTO 05    //Q OK, next line    
            
165    [f] LBL 03    //x=bitmap y=Q position    
166    [h] DSZ Y    //SHIFT QUEEN    
167    [h] GTO 02    //RETRY    
168    INC B    //ootherwise backtrack    
169    RCL->I    //pop a Q    
170    DEC I    //pop a Q    
171    RCL->I    //pop a Q    
172    DEC I    //pop a Q    
173    [h] GTO 03        
            
174    [f] LBL 05    //x=bitmap y=Q position    
175    INC I        
176    STO->I    //Save bitmap    
177    X<>Y        
178    INC I        
179    STO->I    //save Q    
180    X<>Y        
181    DSZ B    //Finish if 0    
182    [h] GTO 01        
183    [h] GTO 04        
            
184    LBL 01        
185    RCL A    //get Q mask    
186    [h] RL->Z    //shift    
187    [h] OR    //merge with bitmap    
188    RCL 00        
189    [h] NOT        
190    [h] AND    //clear combination    
191    [h] RR 09        
192    [h] RRC 08    //shift diagonal    
193    RL 16        
194    [h] RLC 08    //shift diagonal    
195    [h] RR 07        
196    ENTER        
197    ENTER        
198    [h] RL 08        
199    [h] OR    //ORing L V R    
200    ENTER        
201    [h] RL 16        
202    [h] OR    //ORing L V R    
203    RCL 00        
204    [h] AND    //mask Combination    
205    RCL L        
206    [h] XOR    //negate Combination    
207    [f] X=0?    //if 0    
208    [h] GTO 06    //deadend    
209    [h] OR    //merge Combination to bitmap    
210    8        
211    X<>Y        
212    [h] GTO 02        
            
213    [f] LBL 06    //Shortcut    
214    8        
215    STO+C        
216    INC B        
217    RCL->I        
218    DEC I        
219    RCL->I        
220    DEC I        
221    [h] GTO 03        
            
222    [f] LBL 04        
223    RCL C        
224    BASE 10        
225    TICKS        
226    RCL K        
227    -        
228    STO K        
229    R Dn        
230    [g] RTN        
            
bitmap principle            
the bitmap contains 4 parts of 8 bits            
L    Left diagonal locks        
V    Vertical locks        
R    Right diagonal locks        
C    Combination    = L or V or R    This is the part tested (BS?)
            
LLLLLLLVVVVVVVVRRRRRRRRCCCCCCCCL            
register A            
00000001000000010000000100000001            
            
bitmap is rotated to have combination on bits 1 to 8            
register A is rotated too to match bitmap
Queen's positions in registers 4, 6, 8, 10, 12, 14, 16 and 18

P.S. There is also an HP-16C version of this benchmark if you are interested, I am sure that Patrice would be willing to share it.