« Comparison of some Nonogram solvers: Google CP Solver vs Gecode and two MiniZinc solvers | Main | MiniZinc version 1.2 released »

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 (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.py

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:
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 Impact-Based Search (see Philippe Refalo: Impact-Based 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 for parameters.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
P200 was slightly worse in this version: the previous version solved it in 0.14s and with 520 failures. The other two problem was better or about the same with the current version.

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, 9-Dom 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 Impact-Based 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 Paint-by-Number 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: 9-Dom* 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