Comparison of some Nonogram solvers: Google CP Solver vs Gecode and two MiniZinc solvers
After writing Google CP Solver: Regular constraint, Nonogram solver, nurse rostering, etc yesterday, I thought it would be interesting to benchmark the new Nonogram solver written in Google CP Solver with some other solvers. And the benchmark is of course from Jan Wolter's great Survey of PaintbyNumber Puzzle Solvers, though I compare only with Gecode, and two MiniZinc solvers: Gecode/fz (Gecode's FlatZinc solver), and MiniZinc's LazyFD since I know them best and can test them my self.
In the table below, I have kept Wolter's original value is in parentheses to get a feeling for the differences in our machines and to check with my missing problems with Gecode.
System notes:
Please note that I have just tested the problem instances in the existing files for Gecode. Hence a lot of instances where not tested on my machine (they are marked N/A).
Also, I think that Wolter's time for Petro should be 1.4s (not 1.4m).
Note: In contrast to Wolter's result, the times for Gecode/fz and LazyFD includes generating the FlatZinc file, which may be considerable for large problem instances. Hence some of my results are larger for these solvers.
It looks like Google CP Solver/Python solver is quite similar to Gecode/fz solver, and in some case (e.g. 9Dom, Bucks, Tragic, Petro, etc) it has exactly the same number of failures. There are some exceptions, though:
The links for the puzzle is to Wolter's puzzle pages.
In the table below, I have kept Wolter's original value is in parentheses to get a feeling for the differences in our machines and to check with my missing problems with Gecode.
System notes:
 The timeout is 30 minutes as in Wolter's test.
 My machine is a Linux Ubuntu 10.4 LTS with 12Gb RAM, 8 core (Intel i7/930, 2.80GHz), though all programs ran on a single processor.
 Also, I was "working" (Spotify, web surfing, running other tests in parallel, etc) on the machine as the test ran.
 Due to copyrights issues, I cannot distribute the examples. They can be downloaded from Wolter's Sample PaintbyNumber Puzzles Download.
Google CP Solver
Google CP Solver revision 259, with revision 259 of the Python solver nonogram_table2.py, which includes a lot of nice improvements, thanks by Laurent Perron.Gecode
Gecode and Gecode/fz is version 3.4.2 (latest svn revision: 11517)Please note that I have just tested the problem instances in the existing files for Gecode. Hence a lot of instances where not tested on my machine (they are marked N/A).
Also, I think that Wolter's time for Petro should be 1.4s (not 1.4m).
MiniZinc
MiniZinc version: 64bit Linux, snapshot version per 20101105.Note: In contrast to Wolter's result, the times for Gecode/fz and LazyFD includes generating the FlatZinc file, which may be considerable for large problem instances. Hence some of my results are larger for these solvers.
Some comments about Google CP Solver / Python solver
Wolter has done a great job analyzing the three other solvers (Gecode, Gecode/fz, and LazyFD), so I just comment on Google CP Solver solver.It looks like Google CP Solver/Python solver is quite similar to Gecode/fz solver, and in some case (e.g. 9Dom, Bucks, Tragic, Petro, etc) it has exactly the same number of failures. There are some exceptions, though:
 Solved Merka and Dicap quite fast. Gecode/fz timed out for both these problems
 Also solved Flag fast where Gecode/fz timed out. Here it is also faster than LazyFD and Gecode (note: Wolter's time).
 Slower than Gecode/fz on Karate, Signed
 Slightly slower than Gecode/fz on Tragic, with the same number of failures
Comparison  table
Here is the full table. The number in parenthesis is Wolter's times. The second row is my own timing. I also added the number of failures where applicable; LazyFD always returned 0 choice points so I skipped that. A + indicates time out (30 minutes).The links for the puzzle is to Wolter's puzzle pages.
Puzzle  Size  Notes  Gecode  MiniZinc Gecode/fz 
MiniZinc LazyFD 
Google CP Solver 

#1: Dancer*  5 x 10  Line  (0.01s) 0.01s/0 failures 
(0,01s) 0.08s/0 failures 
(0.04s) 0.1s 
0.02s 0 failures 
#6: Cat*  20 x 20  Line  (0.01s) 0.1s/0 failures 
(0.02s) 0.1s/0 failures 
(0.44s) 0.95s 
0.12s 0 failures 
#21: Skid*  14 x 25  Line, Blanks  (0.01s) 0.01s/0 failures 
(0,02s) 0.09s/13 failures 
(0.64s) 0.9s 
0.03s 0 failures 
#27: Bucks*  27 x 23  Blanks  (0.01s) 0.2s/2 failures 
(0.02s) 0.1s/3 failures 
(1.1s) 1.6s 
0.05s 3 failures 
#23: Edge*  10 x 11  (0.01s) 0.01s/15 failures 
(0.01s) 0.09s/25 failures 
(0.08s) 0.16s 
0.03s 25 failures 

#2413: Smoke  20 x 20  (0.01s) N/A 
(0.02s) 0.11s/5 failures 
(0.60s) 1.18s 
0.05s 8 failures 

#16: Knot*  34 x 34  Line  (0.01s) 0.01s/0 failures 
(0.02s) 0.14s/0 failures 
(5.5s) 5.6s 
0.12s 0 failures 
#529: Swing*  45 x 45  Line  (0.02s) 0.02s/0 failures 
(0.04s) 0.24s/0 failures 
(13.2s) 22.3s 
0.3s 0 failures 
#65: Mum*  34 x 40  (0.02s) 0.02s/17 
(0.04s) 0.18s/20 failures 
(11.0s) 12.4s 
0.15s 22 failures 

#7604: DiCap  52 x 63  (0.02s) N/A 
(0.06s) 0.29s/0 failures 
(+) 1:48m 
0.45s 0 failures 

#1694: Tragic  45 x 50  (0.14s) N/A 
(3.6m) 2:14m/394841 failures 
(32.1s) 34.57s 
2:33m 394841 failures 

#1611: Merka*  55 x 60  Blanks  (0.03s) N/A 
(+) + 
(1.1m) 1:10m 
0.47s 27 failures 
#436: Petro*  40 x 35  (1.4m[s?]) 0.05s/48 failures 
(1.6s) 1.15s/1738 failures 
(6.2s) 9.3s 
1.19s 1738 failures 

#4645: M&M  50 x 70  Blanks  (0.93s) N/A 
(0.28s) 0.41s/89 failures 
(48.1s) 1:14m 
0.48s 82 failures 
#3541: Signed  60 x 50  (0.57s) N/A 
(0.56s) 0.61s/929 failures 
(1.0m) 1:02m 
11.7s 6484 failures 

#803: Light*  50 x 45  Blanks  (+) N/A 
(+) + 
(4.7s) 18.32s 
+ 
#6574: Forever*  25 x 25  (4.7s) N/A 
(2.3s) 1.5s/17143 failures 
(1,7s) 1.99s 
1.6s 17143 failures 

#2040: Hot  55 x 60  (+) N/A 
(+) + 
(2.6m) 1:05m 
+  
#6739: Karate  40 x 40  Multiple  (56.0s) N/A 
(57.8s) 38.0s/215541 failures 
(13.6s) 22.52s 
56.1s 215541 failures 
#8098: 9Dom*  19 x 19  (12.6m) N/A 
(3.8s) 2.59s/45226 failures 
(1.8s) 3.11s 
3.9s 45226 failures 

#2556: Flag  65 x 45  Multiple, Blanks  (3.4s) N/A 
(+) + 
(4.2s) 16.18s 
1.6s 14859 failures 
#2712: Lion  47 x 47  Multiple  (+) N/  (+) + 
(+) 8:54m 
+ 
#10088: Marley  52 x 63  Multiple  (+) N/A 
(+) + 
(2.9m) + 
+ 
#9892: Nature  50 x 40  Multiple  (+) N/A 
(+) + 
(2.4m) 25.29s 
+ 