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

[iceman]

Patrice Torchet has optimized the WP-34S benchmark posted above.

Performance statistics using WP34S Firmware version 3.3 on HP-30B Hardware for the "Traditional" WP-34S NQueens Benchmark (See Xerxes Article)

WP-34S "Traditional" mode: [f] H.d (DECM):------------------------>68 Ticks
WP-34S "Traditional" mode: BASE 10 : -----------------------------> 61 Ticks

Performance statistics using WP34S Firmware version 3.3 on HP-30B Hardware for the code below are as follows:

Torchet WP-34S Optimized:-------------------------------------------->21 Ticks

There are approximately 10 Ticks per second

Here is the optimized code:

Code:

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

Merci Patrice, it is a work of beauty!