MiniZinc: 151 new Nonogram problem instances (from JaCoP)
The latest versions of JaCoP (download here) includes 151 Nonogram instances (ExamplesJaCoP/nonogramRepository/). I wrote about these and the included Nonogram solver in JaCoP: a request from the developers (Knapsack and Geost) and Nonogram labeling.
When I (beta) tested the new FlatZinc support for this version, I converted these instances to MiniZinc's data file (.dzn) for some tests. It is a fun way of testing a system.
Now all these problem instances have been published. They are to be used with the MiniZinc Nonogram model nonogram_create_automaton2.mzn. See At last 2: A Nonogram solver using regular written in "all MiniZinc" for more about this model.
All problem instances - in MiniZinc's .dzn format - are available in www.hakank.org/minizinc/nonogram_examples, and also packed in the Zip file nonogram_examples.zip. The name of each file corresponds to the files in JaCoP's
The main call is
which means that statistics should be shown and also require to return all solutions of the problem.
The FlatZinc (.fzn) files was generated from the .dzn files with the following command:
* The Java program ExamplesJaCoP.Nonogram
* Running JaCoP's MiniZinc/FlatZinc solver Fz2jacop
The program instances is, with one exception the same as in the distributed ExamplesJaCoP.Nonogram. Since I wanted both program to solve for all solutions, I excluded instance #83 (see below) since it has too many solutions. However, the P200 problem in included since it is hardwired in ExamplesJaCoP.Nonogram. This means that it it still 151 problems running.
The result:
* ExampleJaCoP.Nonogram took 14.8 seconds
* The Fz2jacop version took 17.8 seconds
I'm quite impressed with both of these results, especially Fz2jacop's As shown in JaCoP: a request from the developers (Knapsack and Geost) and Nonogram labeling, many problems are solved in "0" milliseconds, but still.
When I (beta) tested the new FlatZinc support for this version, I converted these instances to MiniZinc's data file (.dzn) for some tests. It is a fun way of testing a system.
Now all these problem instances have been published. They are to be used with the MiniZinc Nonogram model nonogram_create_automaton2.mzn. See At last 2: A Nonogram solver using regular written in "all MiniZinc" for more about this model.
All problem instances - in MiniZinc's .dzn format - are available in www.hakank.org/minizinc/nonogram_examples, and also packed in the Zip file nonogram_examples.zip. The name of each file corresponds to the files in JaCoP's
ExamplesJaCoP/nonogramRepository/; the file data000.nin is here called nonogram_jacop_data000.dzn, etc. (A larger file, nonogram_examples_with_fzn.zip also includes the generated .fzn files. Note: I used mzn2fzn for MiniZinc version ROTD/2009-09-13 for this. See below how to generate these files.)
Batch running with JaCoP/Fz2jacop
Running many FlatZinc models with JaCoP's Fz2jacop is not optimal because of the overhead of the Java startup. Instead I used a Java program, JaCoPFznTest.java (based on a program from Krzysztof Kuchcinski, one of JaCoP's main developers. Thanks, Kris.).The main call is
fz.main(new String[] {"-s", "-a", m});
which means that statistics should be shown and also require to return all solutions of the problem.
The FlatZinc (.fzn) files was generated from the .dzn files with the following command:
foreach_file 'mzn2fzn -G jacop --data $f -o $f.fzn nonogram_create_automaton2.mzn' '*.dzn'
ExamplesJaCoP.Nonogram vs. JaCoP/Fz2jacop
This time I just compared the run time of the two different approaches for solving Nonograms with JaCoP:* The Java program ExamplesJaCoP.Nonogram
* Running JaCoP's MiniZinc/FlatZinc solver Fz2jacop
The program instances is, with one exception the same as in the distributed ExamplesJaCoP.Nonogram. Since I wanted both program to solve for all solutions, I excluded instance #83 (see below) since it has too many solutions. However, the P200 problem in included since it is hardwired in ExamplesJaCoP.Nonogram. This means that it it still 151 problems running.
The result:
* ExampleJaCoP.Nonogram took 14.8 seconds
* The Fz2jacop version took 17.8 seconds
I'm quite impressed with both of these results, especially Fz2jacop's As shown in JaCoP: a request from the developers (Knapsack and Geost) and Nonogram labeling, many problems are solved in "0" milliseconds, but still.
Instance #83
As mentioned above, problem instance #83 was excluded since it has too many solutions. Here are two of them. It looks like a person (alien?) standing on a spaceship waving.
# #
# #
# # # # # # #
# # # # # # #
# # #
# # # # # # #
# # # # # # #
# # # # # # #
# # # # # #
# # # #
# # #
# # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # #
# # # # # # # # # # # # #
# # #
# # # # #
# # #
# # # # #
# # #
# # # # # # # # #
----------
# #
# #
# # # # # # #
# # # # # # #
# # #
# # # # # # #
# # # # # # #
# # # # # # #
# # # # # #
# # # #
# # #
# # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # #
# # # # # # # # # # # # #
# # #
# # # # #
# # #
# # # # #
# # #
# # # # # # # # #
----------
This output was generated with the (very new) option {noresult} in mzn_show.pl. (This option don't display the real numeric results.)