Solving Nonogram puzzles by using group-based fully probing

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

1. Introduction

Nonogram is a typical picture logical puzzle in which the pixels in the grid must be painted to either white or black to reveal a hidden (Simpson; Wikipedia. Nonogram) picture. When solving a puzzle, the player paints each pixel by considering two constraints, called clues, associated to the row and column intersecting on the pixel. For example, Fig. 1 illustrates a Nonogram puzzle of 8 × 8 grid with row clues (and column clues) shown in the right side (or bottom side) of the grid. In a row/column of the grid, a sequence of consecutive black pixels is called a segment. A clue $(d_{1}, d_{2}, \dots, d_{k})$ indicating the row/column must be painted as k segments, with length $d_{1}, d_{2}, \dots, d_{k}$ , that are separated by any number of white pixels. For example, in Fig. 1, painting pattern $^{'} 11000101^{'}$ of 7th row satisfies the constraint of clue $(2, 1, 1)$ .

Solving Nonogram puzzles efficiently has been considered challenging (Cohen et al., 2008; Wolter, 2009, 2013). Ueda (Ueda and Nagao, 1996) showed that even determining whether a Nonogram puzzle has a solution is NP-complete. Currently, most efficient Nonogram solver programs (Lin and Wu, 2011; Lin et al., 2011; Liu et al., 2012; Wu, 2012; Sun et al., 2012) are based on work (Wu et al., 2013). The authors in Wu et al. (2013) proposed the FP1, FP2, and FP3 relations to help find more paintings on the grid. The backtracking algorithms incorporating the FP relations has been shown can efficiently solve many puzzles.

Fig. 1.

A Nonogram puzzle and the solution painting.

In this paper, we propose a new set of logical properties, called GP relations, to inference the consistent and inverse relations among pixels. These new relations are not intended to directly derive the pixel colors. We show that a pair of pixels with consistent (or inverse) relation must be painted in a same (or an opposite) color in the solution puzzle. The pixels with consistent or inverse relations can be aggregated into groups. Thus, the search tree space of the Nonogram backtracking algorithm can be reduced.

The rest of this paper is organized as follows, Section 2 describes the background of the puzzle game. Section 3 discusses the new GP properties. Section IV describes the backtracking algorithm using the GP properties. Finally, experiments are done in Section 5 and concluding remarks are made in Section 6.

2. Background

2.1. Nonogram puzzles

The Nonogram puzzle is a typical puzzle game that consists of a $w \times w$ square grid with individual entries, called pixels, denoted by $a_{y x}$ , $1 ⩽ x, y ⩽ w$ . In the grid, row y refers to the collection of pixels ${a_{y x} ∣ 1 ⩽ x ⩽ w}$ . Similarly, column x refers to the collection of pixels ${a_{y x} ∣ 1 ⩽ y ⩽ w}$ . A row or a column is also called a line. A line $L_{i}$ refers to row i if $1 ⩽ i ⩽ w$ , and refers to column $i - w$ if $w + 1 ⩽ i ⩽ 2 w$ . The algorithm proposed in this paper can be extended to a rectangular grid with arbitrary height and width straightforwardly.

In a Nonogram puzzle grid, each line $L_{i}$ is associated with a clue $D_{i} = ⟨ d_{i, 1}, d_{i, 2}, \dots, d_{i, k_{i}} ⟩$ , where $d_{i, j} \in Z^{+}$ . In this paper, we ignore the index and simply write $D = ⟨ d_{1}, d_{2}, \dots, d_{k} ⟩$ when the context is clear. The goal of the game is to paint all the pixels in a way that satisfies the constraints on all rows and columns as described as follows.

For a puzzle grid, the colors of the pixels must be $0, 1$ or u, representing color white, black or unknown respectively. Following (Wu et al., 2013), the patterns of the colors of the pixels of a line are expressed using the regular expression notation. For a line L, the painting of the pixels are represented as a string $S_{L} = s_{1} s_{2} \dots s_{w}$ , $s_{i} \in {0, 1, u}$ , $1 ⩽ i ⩽ w$ . A sequence of consecutive 1’s is called a segment. For clue $D = ⟨ d_{1}, d_{2}, \dots, d_{k} ⟩$ , the line L is said solved in terms of D if $S_{L}$ matches the following pattern (Wu et al., 2013): $\begin{matrix} 0^{*} 1^{d_{1}} 0^{+} 1^{d_{2}} 0^{+} \dots 0^{+} 1^{d_{k}} 0^{*} \end{matrix}$ In the above pattern, an asterisk sign (or a plus sign) means repeat the preceding character zero or more times (or at least once). Thus, $0^{+} 1^{d_{j}} 0^{+}$ ( $1 < j < k$ ) represents a pattern consisting of a segment with consecutive $d_{j}$ 1’s that are padded with 0 in the left and right borders. Also, $0 ∣ 1$ matches either 0 or 1.

A Nonogram puzzle is said solved if every line $L_{i}$ is solved for the corresponding clue $D_{i}$ . A grid with all lines solved is called a solution grid and is denoted by $\hat{H}$ . Let $R_{a} \in {0, 1}$ denote the color of pixel a in the solution grid $\hat{H}$ . A partially painted puzzle grid is called an incomplete grid. For two puzzle grids G and $G^{'}$ , the relation $G \to G^{'}$ holds if $G^{'}$ is the same as G but with some u changes to $0 ∣ 1$ on the grid. A grid G satisfying $G \to \hat{H}$ is called a feasible grid, otherwise, conflict grid. For simplicity, this paper assumes that there is only one solution grid $\hat{H}$ for a Nonogram puzzle.

In a Nonogram puzzle, each pixel $a_{y x}$ belongs to two orthogonal lines: row y and column x. Thus, when solving the pixel $a_{y x}$ , it must be painted in a way that both row y and column x match their associated clues. For example, in the puzzle shown in Fig. 1(b), line 3 is painted to 10000111, which satisfies the constraint $D_{3} = ⟨ 1, 3 ⟩$ . In this figure, since the painting of all the lines satisfies the line clues, this painted grid is a solution grid.

2.2. Solving Nonogram puzzles

This subsection describes the concept of the Nonogram algorithm (Wu et al., 2013) briefly.

2.2.1. MaxPaint

A MaxPaint procedure finds the maximal painting of the pixels in a single line by given the line clue. Let ${0, 1, u}$ denote the finite alphabet of painting colors. Let ${0, 1, u}^{w}$ denote the set of all possible strings with length w over ${0, 1, u}$ . A painting string $S \in {0, 1, u}^{w}$ is said partially painted if it contains some u. A string is said matches another string in the sense that u can match 0 or 1, while character $0 / 1$ can only match the same character. Formally, $S = s_{1} s_{2} \dots s_{k} \in Γ^{w}$ matches $S^{'} = s_{1}^{'} s_{2}^{'} \dots s_{k}^{'} \in Γ^{w}$ if and only if $(s_{i} = u) \lor (s_{i} = 0 \land s_{i}^{'} = 0) \lor (s_{i} = 1 \land s_{i}^{'} = 1)$ for all i.

A sequence of consecutive 1’s in a string is called a segment. Given a line L and its clue $D = d_{1}, d_{2}, \dots, d_{k}$ . A string is said satisfy the clue D if it consists of a sequence of k segments, with length $d_{1}, d_{2}, \dots, d_{k}$ , that are separated by 0’s. Given a partially painted string $S \in {0, 1, u}^{w}$ , a string $r \in {0, 1}^{w}$ is called an assignment of S in terms of D if r matches S and satisfies D. Also, let $R_{S, D} = {r ∣ r is an assignment of S and D}$ .

Fig. 2.

The assignments of clue $D = {2, 3}$ on string $S = uu 10 uu 11 uu$ .

Figure 2 shows the set $R_{S, D}$ for $D = (2, 3)$ and $S =^{'} {uu 10 uu 11 uu}^{'}$ . Let us consider the first assignment 0110001110. It contains segments 11 and 111 that are separated by 0’s. Thus it satisfies clue $D = (2, 3)$ . Clearly, it also matches the partially painted string $S =^{'} {uu 10 uu 11 uu}^{'}$ . Thus, it is a valid assignment in terms of S and D.

For the partially painted string $S =^{'} {uu 10 uu 11 uu}^{'}$ shown in Fig. 2, if the painted positions (i.e. the positions with $0 ∣ 1$ ) are known to be in the solution, clearly the final solution painting of this line must be one of the assignments in $R_{S, D}$ . As Fig. 2 illustrates, if $D = (2, 3)$ and $S =^{'} {uu 10 uu 11 uu}^{'}$ is a partial solution, the final solution for this line must be one of the listed 6 assignments. On the contrary, if a position is painted to 0 (or 1) for all assignments, then the solution of this position must be 0 (or 1). For example, in Fig. 2, the solution for position 2 must be 1.

Fig. 3.

Solve pixel b via relation $FP 1$ .

In Wu et al. (2013), Batenburg and Kosters (2009), the authors presented the MaxPaint procedure which, by given a clue D and a partially painted string S, evaluates all the assignments and find the maximum painting efficiently by using the dynamic programming method.

2.2.2. Propagation

In a puzzle grid, each pixel $a_{y x}$ is painted by taking into consideration the clues on the two lines crossing $a_{y x}$ . If a pixel $a_{y x}$ is updated from u to $0 ∣ 1$ after applying MaxPaint on row y, then the orthogonal column x may have chance to solve more pixels. A Propagation procedure consists of a sequence of MaxPaint $M_{1}, M_{2}, \dots, M_{m}$ applied on rows and columns alternatively.

Let a and b a pair of unsolved pixels in an incomplete grid G. If painting pixel a to color $C$ in G leads to painting b to color $D$ via a sequence of propagation operation, $P_{a}, P_{b} \in {0, 1, u}$ and $C, D \in {0, 1}$ , we said that there exists a propagation relation between pixel a and b and denote it by ${(P_{a} = C ⟹ P_{b} = D)}_{G}$ .

According to Wu et al. (2013), the propagation relation states that if we find $R_{a} = C$ is a solution, and we paint pixel b to color $D$ via a sequence of propagation relations connecting a and b, then we can conclude that $R_{b} = D$ . That is, the Propagation procedure can solve more pixels for multiple lines for a partially solved grid. Lemma 1 summaries this property.

Theorem 1 (Wu et al. (2013)).

Let G be a feasible grid satisfying $G \to \hat{H}$ . For a pair of unsolved pixels $a, b$ in G, if $R_{a} = P_{a}$ and ${(P_{a} = C ⟹ P_{b} = D)}_{G}$ then $R_{b} = P_{b}$ .

2.3. Fully-probing deductions

For many Nonogram puzzle grids, the propagation operation ends with some unsolved pixels. In this case, the authors in Batenburg and Kosters (2009), Wu et al. (2013) suggested the guessing and checking approach, called probing. For a pair of unsolved pixels $P_{a}$ and $P_{b}$ in a feasible grid G, the following FP1 property holds (Wu et al., 2013):

FP1: Let $C \in {0, 1}$ , $\begin{array}{l} {(P_{a} = 0 ⟹ P_{b} = C)}_{G} \land \\ {(P_{a} = 1 ⟹ P_{b} = C)}_{G} \\ ⟹ & R_{b} = C \end{array}$

Figure 3 illustrates the notion of relation FP1. Relation FP1 holds in the sense that,

P_{a}

’s color must be either 0 or 1, both leading to

P_{b}

’s color equals to 0. Then, we can conclude that color

C

is the solution for pixel b, i.e.

R_{b} = C

Based on contra-positive logic $p ⟹ q ⟺ \neg q ⟹ \neg p$ , we can write the contra-positive FP relation as follows:

FP2: Let $C, D \in {0, 1}$ ,

\begin{array}{l} {(P_{a} = C ⟹ P_{b} = D)}_{G} \\ ⟺ & {(P_{b} = \neg D ⟹ P_{a} = \neg C)}_{G} \end{array}

FP2 can help solve more pixels as demonstrated in Fig. 4. In Fig. 4(a), we cannot determine the color of pixel

P_{a}

P_{b}

since FP1 does not hold. However, as shown as in Fig. 4(b), if we incorporate the FP2 relation (the dashed edge), we can obtain that

P_{a} = 1

, since both

P_{a} = 0

and

P_{a} = 1

lead to

P_{b} = 1

Fig. 4.

(a) A case that FP1 cannot solve pixel a. (b) Use FP1 and FP2 to solve pixel a. (c) Transitive relation of FP2.

3. Group based probing

This section describes the GP relations (i.e. group based probing relations). Unlike FP relation, which deduces the colors of the pixels, a GP relation deduces the relation between the colors the pixels.

Let $C \in {0, 1}$ , $\neg C$ denotes the reverse color of $C$ (i.e. $\neg 0 = 1$ and $\neg 1 = 0$ ). For a given feasible grid G and two unsolved pixels $a, b \in G$ , the GP1 relation inferences that whether a and b must be painted consistently (i.e. using a same color):

GP1 $\begin{array}{l} {(P_{a} = 0 ⟹ P_{b} = 0)}_{G} \land \\ {(P_{a} = 1 ⟹ P_{b} = 1)}_{G} \\ ⟺ & (R_{a} = R_{b}) \end{array}$

Similarly, the inverse relation inferences whether two pixels must be painted oppositely (i.e. using different colors):

GP2

\begin{array}{l} {(P_{a} = 0 ⟹ P_{b} = 1)}_{G} \land \\ {(P_{a} = 1 ⟹ P_{b} = 0)}_{G} \\ ⟺ & (R_{a} = \neg R_{b}) \end{array}

Fig. 5 illustrates GP1, GP2 and their transitive extension.

Fig. 5.

(a) Relation GP1, (b) Relation GP2, and (c) Transitive GP relation from a to c.

Theorem 2.

For a feasible grid G, both the properties GP1 and GP2 hold.

Proof.

Assume that $\hat{G}$ is a grid satisfying $G \to \hat{G}$ , i.e. $\hat{G}$ is the same as G but with some u turns to $0 ∣ 1$ . Let $G ∣ (P_{a} = C)$ denote the grid G in which the color of pixel a is equal to $C \in {0, 1, u}$ . According to Wu et al. (2013), if the propagation operation paints some colors in a board $G ∣ (P_{a} = u)$ , the propagation operation must also paint the same colors in both of board $G ∣ (P_{a} = 0)$ and board $G ∣ (P_{a} = 1)$ . Thus, the following property holds:

Property Q1: the condition ${(P_{a} = C ⟹ P_{b} = D)}_{G} ⟹ {(P_{a} = C ⟹ P_{b} = D)}_{\hat{G}}$ holds for all $G, \hat{G}$ satisfying $G \to \hat{G}$ .

(Proof of GP1) From Property Q1, if ${(P_{a} = 0 ⟹ P_{b} = 0)}_{G} \land {(P_{a} = 1 ⟹ P_{b} = 1)}_{G}$ then ${(P_{a} = 0 ⟹ P_{b} = 0)}_{\hat{G}} \land {(P_{a} = 1 ⟹ P_{b} = 1)}_{\hat{G}}$ for all $\hat{G}$ , $G \to \hat{G}$ . Thus, the pixels $a, b$ are painted to a same color for all $\hat{G}$ satisfying $G \to \hat{G}$ .

(Proof of GP2) Analogously, from Property Q1, if ${(P_{a} = 0 ⟹ P_{b} = 1)}_{G} \land {(P_{a} = 1 ⟹ P_{b} = 0)}_{G}$ then ${(P_{a} = 0 ⟹ P_{b} = 1)}_{\hat{G}} \land {(P_{a} = 1 ⟹ P_{b} = 0)}_{\hat{G}}$ for all $\hat{G}$ , $G \to \hat{G}$ . Thus, the pixels $a, b$ are painted to a different color for all $\hat{G}$ satisfying $G \to \hat{G}$ .

Fig. 6.

Maintaining groups in backtracking.

Note that in the above, the solution grid $\hat{H}$ also satisfies the property $G \to \hat{H}$ , which concludes that the pixel $a, b$ are painted consistently (GP1) or inversely (GP2) in the solution grid. □

4. Group based backtracking

This section discusses using relation GP1 and GP2 in Nonogram backtracking algorithm.

4.1. Pixel groups

A set of pixels S is said consistent if all the pairs of pixels in S satisfy relation GP1. Clearly, relation GP1 forms a class of pixels in a grid. The GP2 relations between pixels is represented as a pair of sets of pixels. A pixel group (or simply group) consists of two sets of pixels, denoted by $(S, T)$ , in which both S and T are consistent, and each pair of $a \in S$ and $b \in T$ satisfy relation GP2.

From above, for a pixel group $(S, T)$ , all the pixels in set S (and also T) must be painted using a same color, but S and T must be painted in opposite colors. Note that if $(S, T)$ is a pixel group, so does $(T, S)$ . That is, it can be color 0 for S and color 1 for T, or vice versa.

4.2. Backtracking algorithm

Our group based backtracking algorithm is described in Algorithm 1. Given a partially solved grid G, the algorithm traverses a binary search tree recursively, starting from G, in depth first order. At each tree node (i.e. a painting state of the puzzle grid), it selects an unsolved pixel a and generates two branches for $P_{a} = 0$ and $P_{a} = 1$ . For each branch, since there is one more pixel a gets painted, the algorithm tries to paint more pixels by using FP relations. A key element in the success of the backtracking algorithm comes from solving more pixels in each tree node to reduce the scale of the search tree.

Algorithm 1 enhances the performance by aggregating the pixels into groups instead of solving pixels individually. Assume that the backtracking algorithm is processing a current tree node G. In Algorithm 1, line (3)–(5), it selects an unpainted pixel and generates two tree nodes $G_{0}$ and $G_{1}$ . Since $G \to G_{0}$ and $G \to G_{1}$ , all the propagation relations in G remain exist in $G_{0}$ and $G_{1}$ . Therefore, all the GP relations in G remain exist in $G_{0}$ and $G_{1}$ . In Algorithm 1, line (4)(b), it derives new GP relations in $G_{0}$ . Then, it merges the new relations with the old relations (those from G) to construct the new groups.

Algorithm 1

Grouped-Based Backtracking

Figure 6 illustrates an example of maintaining groups in backtracking. In tree node $n_{1}$ , there are two groups 1 and 2, each consists of an S-part (white box) and a T-part (black box). In tree node $n_{2}$ , group 1 and 2 are merged into group 3. In tree node $n_{3}$ , group 3 is unchanged and an additional group 4 is created.

5. Experiments and discussions

We implemented the algorithm and performed tests on the TCGA 2017 Nonogram contest dataset (TCGA Computer Game Tournaments, 2017) which contains 1000 puzzles with uniform distribution on difficulties. In the experimental results, among 1000 puzzles, there are about 50 puzzles contains groups. The group number is usually small, such as range from 2 to 5. Also, in average, the group size ranges from 2–30 pixels.

The experimental results show that the GP backtracking method may not improve the execution time in an order of magnitude. However, in some special puzzle, the GP backtracking may reduce the tree search space significantly.

To summarize, we analysis the costs of using GP relations as follows:

Since both GP and FP relations are defined on the propagation relation, detecting GP1 and GP2 relations do not impose additional propagation costs when compared to the FP relations.

The cost of merging and querying groups can exceeds the cost of painting pixels individually. To overcome the overhead, we suggest only to maintain groups with size greater than 7.

6. Conclusions

This paper proposes the GP relations to inference the consistent and inverse relations among pixels. In the proposed backtracking algorithm, the pixels with consistent or inverse relations can be aggregated into groups. Thus, the search tree space of the backtracking algorithm can be reduced.

References

Batenburg, K.J. & Kosters, W.A. (2009). Solving nonograms by combining relaxations. Pattern Recognit., 42(8), 1672–1683. doi:10.1016/j.patcog.2008.12.003.

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., Sun, D.-J., Wu, I.-C. & Yen, S.-J. (2011). The 2011 TAAI computer-game tournaments. ICGA Journal, 34(1), 51–54. doi:10.3233/ICG-2011-34118.

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.

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).

Simpson, S. Nonogram Solver. Available at: www.comp.lancs.ac.uk/~ss/nonogram/.

Sun, D.-J., Wu, K.-C., Wu, I.-C., Yen, S.-J. & Kao, K.-Y. (2012). Nonogram Tournaments in TAAI 2011. ICGA Journal. To appear.

TCGA Computer Game Tournaments (2017). 2017: Nonogram Tournament Result. Available at: www.tcga.tw/tournament2017/en/.

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.

10.

Wikipedia. Nonogram. Available at en.wikipedia.org/wiki/Nonogram.

11.

Wolter, J. (2009). The ‘pbnsolve’ Paint-by-Number Puzzle Solver. Available at: http://webpbn.com/pbnsolve.html.

12.

Wolter, J. (2013). Effect of Line Solution Caching on Pbnsolve Run-times. Available at: http://webpbn.com/survey/caching.html.

13.

Wu, I.-C., Sun, D.-J., Chen, L.-P., Chen, K.-Y., Kuo, C.-H., Kang, H.-H. & Lin, H.-H. (2013). An efficient approach to solving nonograms. IEEE Transactions on Computational Intelligence and AI in Games, 5(3), 251–264. doi:10.1109/TCIAIG.2013.2251884.

14.

Wu, K.-C. (2012). TAAI2011 Nonogram Tournament Result. Available at: http://kcwu.csie.org/kcwu/nonogram/taai11/.