WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution
10-23-2014, 05:20 PM
Post: #21
 patrice Member Posts: 184 Joined: Dec 2013
RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution
8 Queens on steroids
Breaking news: a little teak dropped the runtime to 1.65s (runs 10 times in 165 ticks) which is about 4 times faster than the non bitmap program for the wp34s.

Code:
148     [f] LBL D        149     [f] BASE 16      150     WSIZE 32         151     [h] CLx  152     STO C           loop counter 153     STO I           Stack pointer 154     1        155     0        156     1        157     0        158     1        159     0        160     1        161     STO A           0x1010101 162     8        163     STO B           remaining Q 164     [h] MASKR 08     165     [h] SL 01        166     STO 00          0x1FE                  167     [f] LBL 02      x=bitmap y=Q position 168     INC C    169     [h] BS?->Y      test Q position 170     [h] GTO 05      Q OK, next line                  171     [f] LBL 03      x=bitmap y=Q position 172     [h] DSZ Y       SHIFT QUEEN 173     [h] GTO 02      RETRY 174     INC B           otherwise backtrack 175     RCL->I          pop a Q 176     DEC I           pop a Q 177     RCL->I          pop a Q 178     DEC I           pop a Q 179     [h] GTO 03                        180     [f] LBL 05      x=bitmap y=Q position 181     INC I    182     STO->I          Save bitmap 183     X<>Y     184     INC I    185     STO->I          save Q 186     X<>Y     187     DEC B 188     RCL A           get Q mask                                 189     [h] RL->Z       shift                                      190     [h] OR          merge with bitmap                          191     RCL 00                                                     192     [h] NOT                                                    193     [h] AND         clear combination                          194     [h] RR 09                                                  195     [h] RRC 08      shift diagonal                             196     RL 16                                                      197     [h] RLC 08      shift diagonal                             198     [h] RR 07                                                  199     ENTER                                                      200     ENTER                                                      201     [h] RL 08                                                  202     [h] OR          ORing L V R                                203     ENTER                                                      204     [h] RL 16                                                  205     [h] OR          ORing L V R                                206     RCL 00                                                     207     [h] AND         mask Combination                           208     RCL L                                                      209     [h] XOR         negate Combination                         210     [f] X=0?        if 0                                       211     [h] GTO 06      deadend                                    212     [h] OR          merge Combination to bitmap                213     8                                                          214     X<>Y                                                       215     [h] GTO 02                                                                                                                 216     [f] LBL 06      Shortcut: all queens locked on the line    217     RCL B                                                      218     X=0?            if B = 0                                   219     GTO 04          finished                                   220     8                                                          221     STO+C                                                      222     INC B           pop a queen                                223     RCL->I                                                     224     DEC I                                                      225     RCL->I                                                     226     DEC I                                                      227     [h] GTO 03                                                                                                                 228     [f] LBL 04                                                 229     RCL C                                                      230     BASE 10                                                    231    [g] RTN
Thanks IceMan for doing the timing
PS: there is still a few drops to squeeze by switching from LBL/GTO to BACK/SKIP.

Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
 « Next Oldest | Next Newest »

 Messages In This Thread WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - iceman - 10-12-2014, 11:38 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - patrice - 10-14-2014, 05:17 AM IMPROVED 30% over previous post - iceman - 10-15-2014, 06:39 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - xerxes - 10-16-2014, 04:30 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - patrice - 10-16-2014, 01:01 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - Claudio L. - 10-16-2014, 06:59 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - patrice - 10-16-2014, 08:53 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - iceman - 10-16-2014, 07:05 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - patrice - 10-17-2014, 08:02 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - Claudio L. - 10-20-2014, 01:07 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - patrice - 10-21-2014, 10:51 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - Claudio L. - 10-22-2014, 01:10 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - patrice - 10-22-2014, 09:15 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - Claudio L. - 10-22-2014, 10:36 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - Claudio L. - 10-23-2014, 10:11 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - Claudio L. - 10-26-2014, 01:55 AM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - xerxes - 10-23-2014, 12:29 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - xerxes - 10-18-2014, 01:36 AM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - Claudio L. - 10-20-2014, 10:05 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - xerxes - 10-21-2014, 09:38 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - patrice - 10-21-2014, 09:49 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - patrice - 10-19-2014, 05:35 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - patrice - 10-23-2014 05:20 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - patrice - 10-24-2014, 11:32 AM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - xerxes - 10-24-2014, 01:00 PM RE: WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution - Thomas Klemm - 10-26-2014, 06:18 AM

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