Nonogram is one type of picture logic puzzle. Naughty is a nonogram solver written by me.
Features & limitation
- Solve black-white nonogram puzzles.
- Can do uniqueness checking (-u).
- Use Steve Simpson's non format as input.
- Maximum puzzle size is 63x63.
- Written in C++. Command line interface.
- Tested on FreeBSD and Linux. Should be easy to build on other systems.
- Open source. Apache license 2.0.
- v88, first public release. Download. Fixed a critical crash bug and some clean up for release. No big difference between v85 and v88.
- v85, participated TAAI2011 nonogram tournament, 2nd place in group A, 3rd place in group B.
- v20, participated TCGA2011 nonogram tournament
Algorithm in brief
- Line solving
- Line states are represented as bit-vector.
- One near O(N) fast line solver using heuristic.
- One O(N*K) complete line solver using dynamic programming.
- Caching solutions of line solver. Even fast line solver can reuse cached results from complete line solver.
- Beyond line solving
- 2-depth contradiction. I think this is the reason naughty is faster than many solvers -- it find more contradictions. However, it is also the reason naughty is slower than LalaFrogKK -- the overhead per search node is very large. I tried very hard to optimize this part.
- Search ordering: one level min-max, counting remain cells. Learned from Yayagram's report.
- and some constant optimization (to reduce redundant computation)
- After discover the color of new cells, don't re-scan whole board. Only check dirty lines.
- When finding 2-depth contradiction, two probes should touch common at least one common row or column.
- Scratch pad, learned from pbnsolve.
- I use MurmurHash as hash function for cache table. MurmurHash was written by Austin Appleby and released to the public domain.
- Jan Wolter's articles on webpbn (especially the survey), his solver, pbnsolve, and his puzzle collections, are very helpful.
I compiled a list of nonogram resources, especially academic papers.