Google CP Solver: A much faster Nonogram solver using DefaultSearch
This is an extension of the comparison done in Comparison of some Nonogram solvers: Google CP Solver vs Gecode and two MiniZinc solvers with includes a new and much faster variant in Google CP Solver.
The day after the above blog post was written, Laurent Perron and I discussed alternative ways of solving these Nonogram problems. Laurent suggested another solving strategy: DefaultSearch (
The changes compared to the previous version nonogram_table2.py was very small in the Python program (there where also some changes in the C++ code). Here are the changes:
This may or may not be a good value for general Nonogram problems. Doing this kind of testing on a limited  albeit mixed  problem set may have biased the search in some unfortunate way.
After deciding on the above heuristics, I finally tested (as a verification set) with some other problem instances and found that they still was easy solved:
As an experiment, I changed the order of variables to
I also experimented with restarts (which is reported to work well with ImpactBased Search), and found some initial promising results. I may come back to this later.
I should also note that the current model is quite different from my first model nonogram_regular.py presented in Google CP Solver: Regular constraint, Nonogram solver, nurse rostering, etc. Laurent has done a great job of optimizing all sort of things, both in the Python code and in the C++ code. For example, he added the "regular like" constraint
In the previous version of the Nonogram solver a couple of the problems timed out, marked + in the table. Some of these, such as Hot and Light, is now solved under 2 seconds. All these "remarkable" improvements in bold.
The links for the puzzle is to Wolter's puzzle pages.
The day after the above blog post was written, Laurent Perron and I discussed alternative ways of solving these Nonogram problems. Laurent suggested another solving strategy: DefaultSearch (
solver.DefaultPhase
) which gave excellent overall result. Then I did some more experiment and tweaking which gave the results shown in the table below.
The new Nonogram model
Model: nonogram_default_search.pyThe changes compared to the previous version nonogram_table2.py was very small in the Python program (there where also some changes in the C++ code). Here are the changes:
parameters = pywrapcp.DefaultPhaseParameters() parameters.heuristic_period = 200000 db = solver.DefaultPhase(board_label, parameters)
DefaultSearch
To be honest, I am not exactly sure why DefaultSearch is so fast for the Nonogram problems. It is a variant of ImpactBased Search (see Philippe Refalo: ImpactBased Search Strategies for Constraint Programming, 2004) combined with periodic heuristics. The source code is here: constraint_solver/default_search.cc.heuristic_period
The value of 200000 forparameters.heuristic_period
was found by experimenting. For quite long I used the value of 11000 and later found that even though increasing this value didn't do much difference for the simpler problems (same time and same number of failures), for the harder problems  such as Lion, Marley, and Nature  the number of failures decreased and the time was improved a bit. Larger values above that, such as 2000000, decreased the number of failures somewhat for the Nature problem, but the time seemed to be slightly worse. So I settled with 200000.
This may or may not be a good value for general Nonogram problems. Doing this kind of testing on a limited  albeit mixed  problem set may have biased the search in some unfortunate way.
After deciding on the above heuristics, I finally tested (as a verification set) with some other problem instances and found that they still was easy solved:
 P200: 0.25s / 1637 failures
 P199: 0.06s / 242 failures
 Dragonfly: 0.03s / 0 failures
As an experiment, I changed the order of variables to
board_flat
(instead of board_label
), then Lion was solved in 2 seconds (compared to 4.45 seconds) and Marley in 11 seconds (compared to 7:18 minutes). On the down side, 9Dom then took 9 seconds (compared to 3.5 seconds) and Nature timed out (compared to 20:25 minutes), and other problems took slightly longer time. So this is probably not a good way to go.
I also experimented with restarts (which is reported to work well with ImpactBased Search), and found some initial promising results. I may come back to this later.
I should also note that the current model is quite different from my first model nonogram_regular.py presented in Google CP Solver: Regular constraint, Nonogram solver, nurse rostering, etc. Laurent has done a great job of optimizing all sort of things, both in the Python code and in the C++ code. For example, he added the "regular like" constraint
solver.TransitionConstraint
which obsoleted my decomposition of regular
for this problem.
A comment on the results
None of the Nonogram solvers that Jan Wolter had tested in his excellent Survey of PaintbyNumber Puzzle Solvers has solved all the problem instances under the 30 minutes time limit. The table below shows that the DefaultSearch variant solves all the problems. At least on my computer, and hopefully also on Wolter's benchmark computer if he want to test this solver. All problems  except Marley and Nature  where solved well under 10 seconds, including the infamous Lion problem (4.46s).In the previous version of the Nonogram solver a couple of the problems timed out, marked + in the table. Some of these, such as Hot and Light, is now solved under 2 seconds. All these "remarkable" improvements in bold.
Test machine
The machine used for the test is the same as in the former test: Linux Ubuntu 10.4 LTS with 12Gb RAM, 8 core (Intel i7/930, 2.80GHz). All programs ran on a single processor. Python version 2.6. Google CP Solver used was revision 276.Comparison  table
Here is the full table with the new version (DefaultSearch) in the last column. The number in parenthesis is Wolter's times. The second row in each entry is my own timing. The number of failures where applicable; LazyFD always returned 0 choice points so these are skipped. 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 
Google CP Solver DefaultSearch 

#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 
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 
0.03s 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 
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 
0.04s 6 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 
0.03s 58 failures 

#2413: Smoke  20 x 20  (0.01s) N/A 
(0.02s) 0.11s/5 failures 
(0.60s) 1.18s 
0.05s 8 failures 
0.04s 20 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 
0.06s 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 
0.11s 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 
0.10s 46 failures 

#7604: DiCap  52 x 63  (0.02s) N/A 
(0.06s) 0.29s/0 failures 
(+) 1:48m 
0.45s 0 failures 
0.18s 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 
0.35s 1862 failures 

#1611: Merka*  55 x 60  Blanks  (0.03s) N/A 
(+) + 
(1.1m) 1:10m 
0.47s 27 failures 
0.20s 96 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 
0.245s 770 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 
0.46s 376 failures 
#3541: Signed  60 x 50  (0.57s) N/A 
(0.56s) 0.61s/929 failures 
(1.0m) 1:02m 
11.7s 6484 failures 
0.92s 3821 failures 

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

#2040: Hot  55 x 60  (+) N/A 
(+) + 
(2.6m) 1:05m 
+  0.62s 2394 failures 

#6739: Karate  40 x 40  Multiple  (56.0s) N/A 
(57.8s) 38.0s/215541 failures 
(13.6s) 22.52s 
56.1s 215541 failures 
0.2s 1361 failures 
#8098: 9Dom*  19 x 19  (12.6m) N/A 
(3.8s) 2.59s/45226 failures 
(1.8s) 3.11s 
3.9s 45226 failures 
3.54s 27650 failures 

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