Solving Nonogram puzzles by using group-based fully probing

Article type: Research Article

Authors: Chen, Lung-Pin^{a; *} | Huang, Kuo-Chan^b

Affiliations: [a] Tunghai University, 40704, Taichung, Taiwan | [b] National Taichung University of Education, Taichung, 40306, Taichung, Taiwan

Correspondence: [*] Corresponding author. E-mails: lbchen2007@gmail.com, lbchen@thu.edu.tw.

Abstract: 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.

Keywords: Backtracking, puzzle game, search tree

DOI: 10.3233/ICG-180067

Journal: ICGA Journal, vol. 40, no. 4, pp. 387-396, 2018