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

[patrice]

Hi Claudio,

(10-20-2014 01:07 PM)Claudio L. Wrote:  I think the array access issue is minor, and doesn't fundamentally change the algorithm (you still have to explore the same number of nodes and do exactly the same tasks.

Take the HP-15C: The single indirection swap in the inner loop imply a mostly 33% overhead. For you, I don't know, but for me, it is NOT MINOR.

(10-20-2014 01:07 PM)Claudio L. Wrote:  I think you should open a new thread and call it the "N-Queens Calculator Competition", (emphasis on "competition" versus "benchmark") where we don't care about comparison or real-world usage, just get the job done with the fastest algorithm optimized the best you can.

It just append that a benchmark IS a competition about being the fastest

Here is an optimized code for the 15C: the algorithm is exactly the same as in the benchmark. It simply use available features more efficiently.

Code:

42,21,11    LBL A
   42 34    CLEAR REG
       8    8
   44 .0    STO .0        
   44  1    STO 1        
42, 6,.1    ISG .1        
   43  7    DEG
   44  8    STO 8
42, 6, 0    ISG 0        
   
42,21, 1    LBL 1        
   45  0    RCL 0
   44 25    STO I
           STO 9
           ISG 9
           DEG
42, 6,.1    ISG .1        

42,21, 2    LBL 2        
   45  8    RCL 8
45,30,24    RCL - (i)
   43 20    x=0?
   22  3    GTO 3        
   43 16    ABS
   45  9    RCL 9
45,30,25    RCL - I
43,30, 5    TEST 5        
   22  3    GTO 3        

42, 5,25    DSE I        
   22  2    GTO 2
42, 6, 0    ISG 0        
   43  7    DEG
   45  0    RCL 0        
   44 25    STO I
   45 .0    RCL .0
43,30, 5    TEST 5        
   22  4    GTO 4        
   
42, 4,24    X<> 8        
        STO (I)
   22  0    GTO 1

42,21, 3    LBL 3        
42, 5, 8    DSE 8        
   22  1    GTO 1
   45  0    RCL 0
   44 25    STO I
   45 24    RCL (I)
   44  8    STO 8
42, 5, 0    DSE 0        
   22  3    GTO 3
42, 5, 1    DSE 1        
42, 6, 0    ISG 0
   43  7    DEG
42, 6,.1    ISG .1        
   43  7    DEG
   22  0    GTO 1
   
42,21, 4    LBL 4        
   45 .0    RCL .0
   44 25    STO I
   43 35    CLX

42,21, 6    LBL 6        
       1    1
       0    0
      20    *
45,40,24    RCL + (I)
42, 5,25    DSE I
   22  6    GTO 6
   45 .1    RCL .1
   43 32    RTN

registres
0    line poiunter
1-8    queens
.0    Size
.1    counter

it saves about 35% of runtime. It don't think it is minor.