Comparison of pbnsolve Versions

Jan Wolter

This is a document, mostly for my own reference, that tracks the performance of various versions of my pbnsolve program. For explainations of the various tests, see my survey of paint-by-number solvers.

Unfortunately, I don't have copies of versions before 1.0.

Pbnsolve Version
pbnsolve 1.10 Blotted clue support. This required some generalization of the line-solving algorithm, and resulted in slightly slower performance.
pbnsolve 1.09 "Plod & Sprint Algorithm".
pbnsolve 1.08 Increase probing to more cells, probing first on all neighbors of cells set since the last probe.
pbnsolve 1.07 Caching of line solver solutions.
pbnsolve 1.06 Minor bug fixes.
pbnsolve 1.05 Scratchpad used during probing, so we don't do a prove if that cell was set to that color during a previous probe.
pbnsolve 1.04 Mostly just fine tuning and tighter coding.
pbnsolve 1.03 Bug fixes and minor code improvements.
pbnsolve 1.02 User interface improvements.

Run Times on Sample Set of Black & White Puzzles
puzzle size Notes pbnsolve 1.10 pbnsolve 1.09 pbnsolve 1.08 pbnsolve 1.07 pbnsolve 1.05/1.06 pbnsolve 1.04 pbnsolve 1.03
#1: Dancer* 5 x 10 Line 0 0 0 0 0 0 0
#6: Cat* 20 x 20 Line 0 0 0 0 0 0 0
#21: Skid* 14 x 25 Line 0 0 0 0 0 0 0
#27: Bucks* 27 x 23   0 0 0 0 0 0 0
#23: Edge* 10 x 11   0 0 0 0 0 0 0
#2413: Smoke 20 x 20   0 0 0 0 0 0 0
#16: Knot* 34 x 34 Line 0 0 0 0 0 0 0
#529: Swing* 45 x 45 Line 0 0 0 0 0 0.01s 0
#65: Mum* 34 x 40   0.01s 0.01s 0.01s 0.01s 0.01s 0.02s 0.01s
#1694: Tragic 45 x 50   0.04s 0.04s 0.03s 0.04s 0.05s 0.10s 0.16s
#1611: Merka* 55 x 60   0.01s 0.01s 0.01s 0.01s 0.01s 0.01s 0.02s
#436: Petro* 40 x 35   0.07s 0.06s 0.06s 0.06s 0.10s 0.11s 0.16s
#4645: M&M 50 x 70   0.07s 0.07s 0.07s 0.07s 0.10s 0.10s 0.18s
#3541: Signed 60 x 50   0.04s 0.04s 0.04s 0.04s 0.04s 0.08s 0.14s
#803: Light 50 x 45   0.39s 0.38s 0.37s 0.68s 0.96s 0.94 1.5s
#6574: Forever* 25 x 25   3.8s 3.7s 9.4s 8.0m 17.0m 18.9m 27.9m
#2040: Hot 55 x 60   0.85s 0.83s 0.82s 0.56s 1.3s 1.8s 2.8s
#6739: Karate 40 x 40 Multiple 0.87s 0.80s 0.79s 3.2s 7.9s 10.3s 14.1s
#8098: 9-Dom* 19 x 19   11.5s 11.0s 10.2s 20.3s 28.3s 39.2s 62.6s
#2556: Flag 65 x 45 Multiple 0.53s 0.55s + + + + +
#2712: Lion 47 x 47 Multiple 6.7s 6.3s 6.0s 44.9s 1.9m 2.9m 4.1m

Run Times on Sample Set of Multicolor Puzzles
puzzle size colors Notes pbnsolve 1.10 pbnsolve 1.09 pbnsolve 1.08 pbnsolve 1.07 pbnsolve 1.05/1.06 pbnsolve 1.04 pbnsolve 1.03
#47: Map 31 x 18 5 Line 0 0 0 0 0 0 0
#220: Onions 40 x 40 5 Line 0 0 0 0 0 0 0
#1503: Bob 25 x 25 3   0.02s 0.01s 0.01s 0.03s 0.04s 0.04s 0.07s
#4364: Snowman 40 x 40 5   0.03s 0.04s 0.03s 0.03s 0.04s 0.05s 0.09s
#2073: Peanut 35 x 35 3   0.04s 0.04s 0.04s 0.03s 0.06s 0.08s 0.14s
#2814: Comet 45 x 50 3   0.08s 0.07s 0.08s 0.08s 0.14s 0.28s 0.42s
#2257: JarJar 55 x 60 3   0.11s 0.10s 0.10s 0.10s 0.19s 0.18s 0.32s
#4940: Babe 45 x 45 3   0.12s 0.11s 0.11s 0.15s 0.27s 0.31s 0.45s
#2817: Shark 50 x 45 3   0.14s 0.13s 0.13s 0.14s 0.21s 0.23s 0.46s
#4445: Pinup 66 x 99 4 Multiple 0.40s 0.40s 0.40s 0.53s 1.1s 2.1s 3.3s
#3149: Ex 40 x 40 5 Multiple 0.63s 0.58s 0.58s 0.26s 0.57s 1.1s 1.5s
#5193: Face 30 x 30 5 Multiple 1.3s 1.3s 1.2s 8.6s 17.3s 25.8s 38.1s
#4809: EFB 50 x 40 4 Multiple 3.4s 3.2s 3.1s 20.3s 57.3s 1.5m 2.1m
#2684: Censored 48 x 64 4 Multiple 7.4s 7.7s 11.8s 19.3s 49.3s 1.6m 2.3m
#2984: Heart 25 x 25 5 Multiple 0.06s 0.05s 0.05s + + + +
#2498: Gecko 75 x 45 5 Multiple 1.5s 1.5s 1.5s + + + +
#3620: Addition 20 x 20 5 Multiple + + + + + + +
#672: Web 52 x 52 4 Multiple + + + + + + +

2,491 Black & White Puzzles
Solver 0 to
0.09 sec		 0.10 to
0.19 sec		 0.20 to
0.49 sec		 0.50 to
0.99 sec		 1.00 to
3.99 sec		 4.00 to
9.99 sec		 10.00 to
29.99 sec		 30.00 to
59.99 sec		 1 min to
2 min		 2 min
or more
pbnsolve 1.10 2469 13 3 4 1 1 0 0 0 0
pbnsolve 1.09 2474 8 3 4 1 1 0 0 0 0
pbnsolve 1.08 2475 7 3 3 0 2 0 0 0 1
pbnsolve 1.07 2471 9 3 4 1 0 0 1 0 2
pbnsolve 1.05/1.06 2443 34 5 3 2 1 0 0 1 2
pbnsolve 1.04 2433 31 16 4 3 0 1 0 0 3
pbnsolve 1.03 2414 28 34 5 6 0 1 0 0 3

3,232 Multicolor Puzzles
Solver 0 to
0.09 sec		 0.10 to
0.19 sec		 0.20 to
0.49 sec		 0.50 to
0.99 sec		 1.00 to
3.99 sec		 4.00 to
9.99 sec		 10.00 to
29.99 sec		 30.00 to
59.99 sec		 1 min to
2 min		 2 min
or more
pbnsolve 1.10 3214 7 2 1 3 1 0 0 0 4
pbnsolve 1.09 3215 6 2 1 3 1 0 0 0 4
pbnsolve 1.08 3214 6 2 1 3 1 1 0 0 4
pbnsolve 1.07 3210 9 2 1 0 2 2 0 0 6
pbnsolve 1.05/1.06 3199 14 6 2 1 1 1 2 0 6
pbnsolve 1.04 3196 12 11 1 2 0 2 0 2 6
pbnsolve 1.03 3186 15 14 4 3 0 1 1 0 8

5,000 Randomly Generated 30x30 Puzzles
Solver 0 to
0.09 sec		 0.10 to
0.19 sec		 0.20 to
0.49 sec		 0.50 to
0.99 sec		 1.00 to
3.99 sec		 4.00 to
9.99 sec		 10.00 to
29.99 sec		 30.00 to
59.99 sec		 1 min to
2 min		 2 min
or more
pbnsolve 1.10 4318 248 176 73 90 37 27 6 5 20
pbnsolve 1.09 4362 221 169 70 88 38 21 6 7 18
pbnsolve 1.08 4357 233 164 71 86 38 20 5 7 19
pbnsolve 1.07 4089 269 215 103 152 47 39 22 10 54
pbnsolve 1.05/1.06 3736 379 302 142 198 74 59 17 27 66
pbnsolve 1.04 3325 622 370 176 223 95 57 29 26 77
pbnsolve 1.03 2835 901 466 222 253 112 68 28 26 89