Naughty - nonogram solver

Nonogram is one type of picture logic puzzle. Naughty is a nonogram solver written by me.

Features & limitation

Solving
- Solve black-white nonogram puzzles.
- Can do uniqueness checking (-u).
- Use Steve Simpson's non format as input.
- Maximum puzzle size is 63x63.
General
- 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

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.