Some new models, etc
The readers that follows me on Twitter (hakankj) have probably already has seen this, but here follows a list of models, etc, not yet blogged about.
Today my Nonogram model nonogram_create_automaton2.mzn was included in the great Survey of Paint-by-Number Puzzle Solvers (created by Jan Wolter).
My MiniZinc model is described and analyzed here. I'm not at all surprised that it's slower compared to the other solvers; it was quite expected.
Some comments:
I later realized two things:
1) That the
2) When Jan compiled Gecode, he set off all optmization for comparison reason. This is quite unfortunate since Gecode is crafted with knowledge of the specific optimizations.
I there have run all problems by myself and see how well it would done (at least the ballpart figure) when using an "normal" optimized Gecode and with the
Explanation of the values:
Problem: Name of the problem instance
Runtime: The value of runtime from Gecode/FlatZinc solver
Solvetime: The value of solvetime from Gecode/FlatZinc solver
Failures: Number of failures:
Total time: The Unix time for running the complete problem, including the time of mzn2fzn (which was not included in the benchmark).
A "--" means that a solution was not reached in 10 minutes.
It's interesting to note that the Lazy solver finds some solutions quite fast for the "Flag" problem. However, there where no other big differences compared to Gecode/FlatZinc. I also tested the problems with JaCoP's FlatZinc solver which solved the problems in about the same time as Gecode/FlatZinc with no dramatic differences.
As mentioned above, the exact values is not really comparable to the benchmark values. But it should give an indication of the result when using
Unfortunately, I cannot link to the specific models due to copyright issues, but they can all be downloaded from the page Web Paint-by-Number Puzzle Export.
(End update)
Update 2009-11-02
Jan Wolter now have rerun the tests of my solver with the
(End update 2)
Also, the Gecode nonogram solver is included in the survey: called Lagerkvist. I'm not sure when it was added to the survey. It use the latest version of Gecode, so it must have been quite recent.
Some comments:
Thanks to Christian Schulte my Word square model is now much faster: word_square2.cpp.
From the comment in the model:
In the SVN trunk version of Gecode, there is now a version of this model:
MiniZinc: Different models
The following four models are translation of my Comet models:- kenken2: Kenken puzzle
- kakuro.mzn: Kakuro puzzle
- killer_sudoku.mzn: Killer Sudoku
- tourist_site_competition.mzn: Tourist Site Competition. This is from Pierre Flener's presentation Constraint Technology - A Programming Paradigm on the Rise (PDF).
-
fill_a_pix.mzn: Fill-a-Pix (yet another fill a grid puzzle)
Data files:
- checker_puzzle.mzn: Checker puzzle from Math Overflow Placing checkers with some restrictions.
- einav_puzzle.mzn: Solving the problem from Geoff Canyon's A programming puzzle from Einav. See the comments in the blog post for some more details.
Nonogram related
A large 40x50 Nonogram problem instance in MiniZinc: nonogram_stack_overflow.dzn to be used with nonogram_create_automaton2.mzn model. The problem was mentioned in Stack Overflow thread Solving Nonograms (Picross). It is solved in under 1 second and 0 failures.Today my Nonogram model nonogram_create_automaton2.mzn was included in the great Survey of Paint-by-Number Puzzle Solvers (created by Jan Wolter).
My MiniZinc model is described and analyzed here. I'm not at all surprised that it's slower compared to the other solvers; it was quite expected.
Some comments:
Assessment: Slow on more complex puzzles.Update 2009-11-01
...
Results: Run times are not really all that impressive, especially since it is only looking for one solution, not for two like most of the other programs reviewed here. I don't know what the differences are between this and Lagerkvist's system, but this seems much slower in all cases, even though both are ultimately being run in the Gecode library.
I later realized two things:
1) That the
mzn2fzn translator did not use the -G gecode flag, which means that Gecode/FlatZinc uses a decomposition of the regular constraint instead of Gecode's built in, which is really the heart in this model. The model is basically two things: build an automata for a pattern and then run regular on it.2) When Jan compiled Gecode, he set off all optmization for comparison reason. This is quite unfortunate since Gecode is crafted with knowledge of the specific optimizations.
I there have run all problems by myself and see how well it would done (at least the ballpart figure) when using an "normal" optimized Gecode and with the
-G gecode flag for mzn2fzn.
Explanation of the values:
Problem: Name of the problem instance
Runtime: The value of runtime from Gecode/FlatZinc solver
Solvetime: The value of solvetime from Gecode/FlatZinc solver
Failures: Number of failures:
Total time: The Unix time for running the complete problem, including the time of mzn2fzn (which was not included in the benchmark).
A "--" means that a solution was not reached in 10 minutes.
| Problem | Runtime | Solvetime | Failures | Total time |
| Dancer | 0.002 | 0.000 | 0 | 1.327s |
| Cat | 0.009 | 0.002 | 0 | 0.965s |
| Skid | 0.012 | 0.006 | 13 | 0.660s |
| Bucks | 0.015 | 0.004 | 3 | 0.866s |
| Edge | 0.008 | 0.005 | 25 | 0.447s |
| Smoke | 0.011 | 0.004 | 5 | 0.963s |
| Knot | 0.026 | 0.006 | 0 | 1.450s |
| Swing | 0.059 | 0.012 | 0 | 1.028s |
| Mum | 0.120 | 0.093 | 20 | 1.811s |
| Tragic | 6:24.273 | 6:23.607 | 394841 | 6:28,10 |
| Merka | -- | -- | -- | -- |
| Petro | 2.571 | 2.545 | 1738 | 4.071s |
| M&M | 0.591 | 0.510 | 89 | 1.961s |
| Signed | 1.074 | 1.004 | 929 | 2.461s |
| Hot | -- | -- | -- | -- |
| Flag | -- [lazy solver: 2 solutions in 10 seconds] | -- | -- | -- |
| Lion | -- | -- | -- | -- |
It's interesting to note that the Lazy solver finds some solutions quite fast for the "Flag" problem. However, there where no other big differences compared to Gecode/FlatZinc. I also tested the problems with JaCoP's FlatZinc solver which solved the problems in about the same time as Gecode/FlatZinc with no dramatic differences.
As mentioned above, the exact values is not really comparable to the benchmark values. But it should give an indication of the result when using
-G gecode and a "normal" optimized Gecode.
Unfortunately, I cannot link to the specific models due to copyright issues, but they can all be downloaded from the page Web Paint-by-Number Puzzle Export.
(End update)
Update 2009-11-02
Jan Wolter now have rerun the tests of my solver with the
-G gecode option, and the time is much more like mine in the table above. The analysis is quite different with an assessment of Pretty decent, and the following under Result:...
When comparing this to other solvers, it's important to note that nonogram_create_automaton2.mzn contains only about 100 lines of code. From Kjellerstrand's blog, it is obvious that these 100 lines are the result of a lot of thought and experimentation, and a lot of experience with MiniZinc, but the Olšák solver is something like 2,500 lines and pbnsolve approaches 7,000. If you tried turning this into a fully useful tool rather than a technology demo, with input file parsers and such, it would get a lot bigger, but clearly the CSP approach has big advantages.
(End update 2)
Also, the Gecode nonogram solver is included in the survey: called Lagerkvist. I'm not sure when it was added to the survey. It use the latest version of Gecode, so it must have been quite recent.
Some comments:
Assessment: Pretty decent.I mailed Jan today about the
...
Puzzles with blank lines seem to cause the program to crash with a segmentation fault.
Otherwise it performs quite well. There seems to be about 0.02 seconds of overhead in all runs, so even simple puzzles take at least that long to run. Aside from that, it generally outperforms the Wilk solver. It's not quite in the first rank, especially considering that it was only finding one solution, not checking for uniqueness, but it's still pretty darn good.
...
-solutions n options in the Gecode related solvers (he tested my MiniZinc model with Gecode/FlatZinc), as well as some other comments about my model. Also, I will download the problems tested and play with them.
Tailor/Essence': Zebra puzzle
Suddenly I realized that there where no Zebra problem, neither at Andrea's or here. So here it is: zebra.eprime: Zebra puzzle.Gecode: Words square problem
See Gecode: Modeling with Element for matrices -- revisited for an earlier discussion of this problem.Thanks to Christian Schulte my Word square model is now much faster: word_square2.cpp.
From the comment in the model:
Christian Schulte suggested using branch strategy INT_VAL_SPLIT_MIN instead of INT_VAL_MAX . This made an improvement for size 7 from 322 failures to 42 and from 1:16 minutes to 10 seconds (for 1 solution). Now it manage to solve a size 8 in a reasonable time (1:33 minutes and 1018 failures): abastral bichrome achiotes shippers troponin rotenone amerinds lessnessBut wait, there's more!
In the SVN trunk version of Gecode, there is now a version of this model:
examples/word-square.cpp where Christian Schulte and Mikael Zayenz Lagerkvist has done a great job of improving it (using a slighly smaller word list, though). It solves a size 8 problem in about 14 seconds. There is also two different approaches with different strengths, etc. I have great hopes that it will improved even further...