Nonogram is a typical two-dimensional logical puzzle game in which each pixel involves two constraints associated to the intersecting row and column. The recently proposed approaches can efficiently solve many puzzles via logical deduction based on the 2-SAT formulas. This paper proposes a set of new logical properties for inferencing the consistent and inverse relations among pixels. We show that the pixels with consistent (or inverse) relation must be painted to a same (or an opposite) color in the solution puzzle. Consequently, the pixels can be aggregated into groups, thereby the space of search tree of the Nonogram backtracking algorithm can be reduced.
Cohen, D., Jeavons, P. & Gyssens, M. (2008). A unified theory of structural tractability for constraint satisfaction problems. Journal of Computer System Sciences, 74(5), 721–743.
Lin, H.-H. & Wu, I.-C. (2011). An efficient approach to solving the minimum su oku problem. ICGA Journal, 34(4), 191–208. doi:10.3233/ICG-2011-34403.
5.
Liu, T.-Y., Wu, I.-C. & Sun, D.-J. (2012). Solving the Slitherlink Problem. In Proceedings of the 2012 Conference on Technologies and Applications of Artificial Intelligence (TAAI 2012), November 16–18, 2012 (pp. 284–289).
Ueda, N. & Nagao, T. (1996). NP-completeness Results for Nonogram via Parsimonious Reductions. TR96-0008, Technical Report, Department of Computer Science, Tokyo Institute of Technology.
