Exploring effects of fully probing sequence on solving nonogram puzzles

Abstract

This paper presents our experimental studies on improving the speed of solving nonogram puzzles. Our approach is based on the algorithm developed by Wu et al. A puzzle solving program, named LalaFrogKK, implementing the algorithm has won several nonogram tournaments since 2011. The algorithm consists of three major parts: propagation based on line solving, fully probing, and backtracking. Fully probing, running before backtracking, contributes to solving a nonogram puzzle in two ways. The first is to paint more pixels after propagation. The second is testing each unpainted pixel for providing backtracking with more accurate guidance when choosing pixels to guess. However, we found that different probing sequences can lead to significant differences in the numbers of painted pixels after fully probing. Therefore, in this paper, we investigate into the effects of different fully probing sequences, and propose several new fully probing mechanisms. Experimental results show that the new mechanisms can significantly outperform the original fully probing method. One of the new fully probing mechanisms achieves a speedup of more than two times in solving nonogram puzzles.

Keywords

Nonogram propagation fully probing backtracking

1. Introduction

Nonogram (2017) is a kind of popular logic puzzles represented on a rectangular grid with clues given as row and column constraints. Solving a nonogram puzzle is to paint all the pixels in the corresponding grid in black and white while satisfying the given row and column constraints. Figure 1 illustrates a solved nonogram puzzle, where in a 5×5 grid row constraints are given in the leftmost column and column constraints are given in the top row. The integers in the clues are used to indicate the lengths of consecutive black pixels in a row or a column in the solution. For example, the constraints of the third row, 2 1, indicate that the row in the solution should have exactly two segments of consecutive black pixels, starting from the left, where the length of the first segment is 2 and that of the second segment is 1. It is possible that a nonogram puzzle has more than one solution all satisfying the constraints.

Solving a nonogram puzzle is an NP-complete problem (Ueda & Nagao, 1996). There have been several challenging nonogram tournaments held in academic conferences since 2011 (Lin, Sun, Wu & Yen, 2011). LalaFrogKK is a nonogram solver developed by Wu et al., which has won several nonogram tournaments since 2011. The nonogram solving algorithm implemented in LalaFrogKK was published in Wu et al. (2013) in 2013. In general, a nonogram puzzle might have more than one solution. Therefore, the pixels in a nonogram puzzle can be divided into two types: the ones with unique solutions, i.e. the same value in all solutions, and the others with alternative solutions, i.e. either 0 or 1 in different solutions. For those pixels potentially having alternative solutions, their solutions might have interrelationship and depend on each other under the row and column constraints.

Fig. 1.

A $5 \times 5$ nonogram puzzle.

The algorithm in Wu et al. (2013) consists of three major parts: propagation based on line solving, fully probing, and backtracking. The first two parts are used to paint as many as possible those pixels with unique solutions. Propagation tries to figure out the solution of a pixel based on the constraints of a single row or column. It involves repeatedly painting pixels with unknown values into 0 or 1 until no more pixels in the grid can be painted. After no more pixels can be painted, a common approach in previous works is to employ backtracking to search all possible solutions. However, in Wu et al. (2013) fully probing is proposed to be used before backtracking. Fully probing attempts to guess a value, i.e. 0 or 1, on each pixel to see whether more pixels can then be painted. Fully probing is different from backtracking in that it is not recursive. Each pixel is only tested once to provide backtracking with more accurate guidance when choosing pixels to guess. In contrast to propagation, fully probing determines the solutions of pixels considering the entire board. For those pixels with alternative solutions, backtracking is used to guess an appropriate value for each pixel one at a time recursively, satisfying the row and column constraints and taking into consideration the interrelationship among pixels.

Among the three parts of the algorithm in Wu et al. (2013), fully probing contributes to solving a nonogram puzzle in two ways. First, some pixels which cannot be painted in the propagation process can be determined their solutions in the fully probing step since fully probing adopts more aggressive guesses and considers information of the entire board. Second, fully probing is used to test each unpainted pixel for providing backtracking with more accurate guidance when choosing pixels to guess, since the guessing sequence could have big impact on the time consumed by the entire backtracking process as shown in Wu et al. (2013). However, we found that the performance of fully probing and the number of painted pixels after fully probing are also affected greatly by the sequence adopted to probe the unpainted pixels. Therefore, we explored the effects of different fully probing sequences, designed and evaluated several new fully probing mechanisms. Compared to the original fully probing method in Wu et al. (2013), experimental results show that one of the new fully probing mechanisms has potential to achieve a speedup of more than two times when solving 1000 nonogram puzzles.

2. Related work

Nonogram, invented by Non Ishida in 1988, is a kind of popular and challenging logic puzzles (Nonogram, 2017), which has been shown to be NP-complete in Ueda & Nagao (1996). Some researchers tried to solve nonogram puzzles by translating them into other classical problems. For example, Bosch translated the nonogram solving problem into an integer linear programming problem for solution in Bosch (2001). Another example is that Faase (2009) translated it into an exact cover problem and then used Knuth’s dancing-links method (Knuth, 1999) to solve it. However, nonogram puzzles usually cannot be solved efficiently by using these kinds of problem transformations, especially for large nonogram puzzles.

Meta-heuristic algorithms are another type of approaches used to solve nonogram puzzles. For example, Batenburg (2007) modified an evolutionary algorithm and Wiggers (2004) used a genetic algorithm to solve nonogram puzzles. Similar works can be found in Tsai, Chou & Fang (2012), Tsai (2012), Tsai & Chou (2011). However, one potential drawback of these approaches is that they might not guarantee to solve a puzzle.

Another kind of approaches are based on logical rules. For example, Yu et al. (2009) developed an algorithm to solve nonogram puzzles based on specific logical rules first, and then use backtracking to find the solutions of unpainted pixels with the set of logical rules for improving search efficiency. Jing (2009) divided the entire process of solving a nonogram puzzle into two parts. In the first part, logical rules were used to paint some pixels first. The remaining unpainted pixels were then solved using a depth first search method enhanced by the branch and bound mechanism in the second part. These logical rules are usually focused on painting a row or a column, aiming at painting as many pixels as possible in each line. There are other simpler line painting methods proposed in Olšák & Olšák (2003), Simpson (2015), which, however, cannot guarantee painting as many pixels as in Yu, Lee & Chen (2009), Jing (2009) for each row or column.

For line solving to paint as many pixels as possible for each row or column, Batenburg and Kosters (2009) adopted a dynamic programming approach instead of using logical rules. In general, their approach paints more pixels than those in Olšák & Olšák (2003), Simpson (2015), Yu, Lee & Chen (2009), and leads to faster execution speed. Batenburg and Kosters (2009) also used a 2-Satisfiability method to paint more pixels before the backtracking stage. Information of many nonogram solvers can be found in Wolter (2012). Generating nonogram puzzles is also an important issue for conducting nonogram solving research. Several nonogram-generating algorithms are discussed in Batenburg, Henstra, Kosters & Palenstijn (2009).

Wu et al. (2013) proposed a nonogram solving approach consisting of three major parts: propagation based on line solving, fully probing, and backtracking. They developed a faster dynamic programming method for line solving based on previous research in Batenburg & Kosters (2009). Three fully probing methods were also proposed for painting more pixels before the backtracking part. In addition to painting more pixels after the propagation part, fully probing also provides the later backtracking stage with useful information about which pixel to guess first in order to find the solution of a nonogram puzzle more quickly.

3. Effects of different fully probing sequences on the speed of solving nonogram puzzles

The idea of fully probing in Wu et al. (2013) is to make guesses for all unpainted pixels, and then perform propagation for each guessed value of each unpainted pixel. The first proposed fully probing method in Wu et al. (2013), named FP1, is described as follows.

procedure FP1(G)

Initialize G p,0, G p,1 for all unpainted pixel p

repeat

PROPAGATE(G)

if (status(G) is CONFLICT or SOLVED) then return

UPDATEONALLG(G)

for (each unpainted pixel p in G) do

PROBE(p)

if (status(G) is CONFLICT or SOLVED) then return

if (status(G) is PAINTED) then break

end for

until $Π (G) = \emptyset$

end procedure

Procedure PROBE(p)

PROBEG(p,0); //guess $p = 0$ and probe G p,0

PROBEG(p,1); //guess $p = 1$ and probe G p,1

if (both status(G p,0) and status(G p,1) are CONFLICT)

then status(G) ← CONFLICT; return

if (status(G p,0) is CONFLICT) then

Let Π be the set of newly painted pixels in G p,1 with respect to G

else if (status(G p,1) is CONFLICT) then

Let Π be the set of newly painted pixels in G p,0 with respect to G

else

Let Π be the set of pixels with the same value 0 or 1 in both G p,0 and G p,1 with respect to G

end if

if ( $Π \neq \emptyset$ ) then UPDATEONALLG(Π); ststus(G) ← PAINTED

else status(G) ← INCOMPLETE

end procedure

FP1 repeatedly probes the unpainted pixels until no more pixels can be painted as described between lines 2 and 11. Π(G) is the set of newly painted pixels in G by propagation. UpdateOnAllG(G) is used to make sure that probing each unpainted pixel is conducted on the most updated board. The procedure Probe probes, respectively, each guessed value, i.e. 1 or 0, of every unpainted pixel by the procedure ProbeG which simply performs propagation on the board updated with the guessed value.

The for-loop between lines 6 to 10 in FP1 simply indicates that each unpainted pixel should be probed, but does not specify a specific probing sequence among all unpainted pixels. However, we found that different probing sequences could lead to large performance difference in solving nonogram puzzles as shown in Table 1. We used the program, LalaFrogKK, available at Wu (2015) to evaluate four different probing sequences on three puzzle sets used in different nonogram tournaments, each containing 1000 puzzles. For the probing sequence indicated by rowwise left-to-right in Table 1, the unpainted pixels are traversed rowwise starting from the leftmost unpainted pixel on each row. Columnwise top-to-bottom means that the traversal proceeds columnwise beginning from the top unpainted pixel on each column.

Table 1
Performance of different probing sequences measured in seconds

Probing sequence TAAI 2013 TCGA 2013 TCGA 2017

Rowwise left-to-right 4694.96 1341.72 8324.97

Rowwise right-to-left 3263.47 1387.76 7938.63

Columnwise top-to-bottom 3592.54 1390.63 8339.34

Columnwise bottom-to-top 3436.86 1349.15 7953.42

Probing sequence	TAAI 2013	TCGA 2013	TCGA 2017
Rowwise left-to-right	4694.96	1341.72	8324.97
Rowwise right-to-left	3263.47	1387.76	7938.63
Columnwise top-to-bottom	3592.54	1390.63	8339.34
Columnwise bottom-to-top	3436.86	1349.15	7953.42

Our investigation shows that performance difference among different probing sequences results from the fact that different probing sequences would lead to diverse numbers of painted pixels after fully probing. An illustrated example is shown in Fig. 2 and Fig. 3, which represent the board statuses after fully probing by rowwise left-to-right and rowwise right-to-left, respectively. Significant difference can be seen in the two boards in Fig. 2 and Fig. 3, indicated by the shaded area where $- 1$ represents an unpainted pixel.

The above findings motivated us to explore the effects of fully probing sequences on the speed of solving a nonogram puzzle. In general more painted pixels after the fully probing procedure could have large potential to reduce the computation cost of the following backtracking process. However, if more painted pixels are achieved at the cost of a more complicated fully probing process, the effects on the total time required to solve a nonogram puzzle is unclear since the backtracking procedure in Wu et al. (2013) also invokes the fully probing procedure after each guess of an unpainted pixel. Therefore, we designed three new fully probing mechanisms as follows for exploring the best balance between painting more pixels and keeping the fully probing procedure simple.

Fig. 2.

Board by rowwise left-to-right.

Fig. 3.

Board by rowwise right-to-left.

One_run. In this mechanism, the outer repeat-until loop on lines 2 and 11 in FP 1 (Wu et al., 2013) is discarded. Lines 3 to 5 are also deleted. Therefore, the for loop between lines 6 and 10 becomes the body of the fully probing procedure. Line 9 is no longer needed since there is no outer loop to break. Without the outer repeat-until loop, this new fully probing mechanism simply probes each unpainted pixel for once, speeding up the entire procedure at the cost of painting less pixels after fully probing.

Repeat_no_break. This mechanism simply discards line 9 in the original FP 1 (Wu et al., 2013). It can reduce the times of the outer repeat-until looping and thus the times of probing unpainted pixels. This mechanism could hopefully paint as more pixels as the original FP1 in Wu et al. (2013) since it also comes to an end only when no more pixels can be painted after all unpainted pixels have been probed for once.

Selective_repeat. This mechanism tries to reduce computation cost of the entire fully probing procedure by probing only the related unpainted pixels in the inner for-loop of FP1 (Wu et al., 2013). Related unpainted pixels are considered to be those located at the row and column crossing on some newly painted pixel in an iteration of the outer repeat-until loop. Only those related unpainted pixels will be re-probed in the next iteration of the repeat-until loop. It is likely that this mechanism does not paint as more pixels as the original FP1 (Wu et al., 2013) since not all unpainted pixels are re-probed in each iteration of the repeat-until loop.

4. Performance evaluation

Table 2 presents the performance results, measured in seconds, of evaluating the three new fully probing mechanisms, compared to the original FP1 in Wu et al. (2013), each solving the same set of 1000 nonogram puzzles. It is obvious that different fully probing sequences lead to large performance difference. Our selective-repeat mechanism outperforms all the other fully probing mechanisms, achieving a speedup of more than two times compared to the original FP1 method in Wu et al. (2013).

To investigate into the causes of the performance difference shown in Table 2, we analyzed related data of several aspects collected throughout the fully probing procedure, which are shown in Table 3. The measured data include the number of painted pixels after fully probing and the number of probes conducted on unpainted pixels during the fully probing process. It is clear that the original FP1 and our repeat_no_break mechanism both paint the greatest number of pixels after fully probing. However, our selective_repeat mechanism paints almost the same number of pixels as original FP1 and the repeat_no_break mechanism, except puzzle #309, but at a much less computation cost reflected by the smaller number of probes conducted throughout the entire fully probing procedure. Therefore, the selective_repeat mechanism achieves the best performance as shown in Table 2. For the one_run mechanism, it takes the least number of probes to finish fully probing at the cost of much less painted pixels after fully probing. Therefore, it leads to worse performance than the repeat_no_break and selective_repeat mechanisms as shown in Table 2. All the three new fully probing mechanisms outperform the original FP1 methods (Wu et al., 2013) significantly.

Table 2
Performance results of different fully probing mechanisms

Original FP1 (Wu et al., 2013 ) One_run Repeat_no_break Selective_repeat

Execution time 4724 3720 2149 1918

	Original FP1 (Wu et al., 2013 )	One_run	Repeat_no_break	Selective_repeat
Execution time	4724	3720	2149	1918

Table 3

Performance data regarding fully probing

	Puzzles	Original FP1 (Wu et al., 2013 )	One_run	Repeat_no_break	Selective_repeat
Number of painted pixels	#301	362	329	362	362
	#302	122	104	122	122
	#303	312	309	312	312
	#304	331	236	331	331
	#309	191	160	191	190
Number of probes	#301	8537	376	1190	949
	#302	3426	558	1571	1275
	#303	4369	381	1009	706
	#304	15627	431	1366	1230
	#309	7398	493	2278	1520

5. Conclusions and future work

We explored the effects of different fully probing sequences on solving nonogram puzzles, and developed three new fully probing mechanisms. Experimental results show that different fully probing sequences could have large impact on the performance of solving nonogram puzzles. All our three fully probing mechanisms outperform the original FP1 method in Wu et al. (2013) significantly, and the selective_repeat mechanism achieves a speedup of more than two times. In contrast to other methods which probe each unpainted pixel, the selective_repeat mechanism probes only those unpainted pixels considered most promising to paint more pixels. Therefore, it can paint almost the same number of pixels as the original FP1 method (Wu et al., 2013) at a much less computation cost, resulting in the significant performance improvement.

Our work in this paper demonstrates that the fully probing sequence can greatly affect the speed of solving nonogram puzzles. However, more research work is needed and promising to further improve the performance of solving nonogram puzzles. For example, our selective_repeat mechanism would paint a slightly less number of pixels than the original FP1 method (Wu et al., 2013) before going into backtracking for some nonogram puzzles, e.g. #309 in Table 3. It would be interesting and challenging to develop a new fully probing mechanism which could always paint the same number of pixels as the original FP1 method (Wu et al., 2013), but at a much less computation cost. Moreover, we found it seems that not all the pixels with unique solutions can be painted before backtracking. Developing new methods to paint all the pixels with unique solutions before backtracking would greatly improve the nonogram solving performance and thus is a worthful future research direction. We also found that more painted pixels sometimes could not guarantee less computation costs in the backtracking stage, worthwhile further investigation work.

References

Batenburg, K.J. (2007). A network flow algorithm for reconstructing binary images from discrete X-rays. J. Math. Imag. Vis., 27(2), 175–191. doi:10.1007/s10851-006-9798-2.

Batenburg, K.J., Henstra, S., Kosters, W.A. & Palenstijn, W.J. (2009). Constructing simple nonograms of varying difficulty. Pure Math. Appl., 20, 1–15.

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.

Bosch, R.A. (2001). Painting by numbers. Optima, 65, 16–17.

Faase, F. (2009). Nonogram to exact cover. Retrieved March 31, 2018, from http://www.iwriteiam.nl/D0906.html#28.

Jing, M.Q. (2009). Solving Japanese puzzles with logical rules and depth first search algorithm. In International Conference on Machine Learning and Cybernetics (pp. 2962–2967).

Knuth, D.E. (1999). Dancing links. In Millennial Perspectives in Computer Science: The Oxford-Microsoft Symposium in Honour of Sir Tony Hoare (Cornerstones of Computing) (pp. 187–214). Basingstoke, U.K.: Palgrave.

Lin, H.H., Sun, D.J., Wu, I.C. & Yen, S.J. (2011). The 2011 TAAI computer-game tournaments. Int. Comput. Games Assoc. J., 34(1), 51–54.

Nonogram. (2017). In Wikipedia, the free encyclopedia. Retrieved March 31, 2018, from http://en.wikipedia.org/wiki/Nonogram.

10.

Olšák, M. & Olšák, P. (2003). Griddlers solver. Retrieved March 31, 2018, from http://www.olsak.net/grid.html#English.

11.

Simpson, S. (2015). Nonogram solver. Retrieved March 31, 2018, from http://www.lancaster.ac.uk/~simpsons/software/pkg-nonowimp.htmlz.en-GB.

12.

Tsai, J. (2012). Solving Japanese nonograms by Taguchi-based genetic algorithm. Appl. Intell., 37(3), 405–419. doi:10.1007/s10489-011-0335-7.

13.

Tsai, J. & Chou, P. (2011). Solving Japanese puzzles by genetic algorithms. In International Conference on Machine Learning and Cybernetics (pp. 785–788).

14.

Tsai, J., Chou, P. & Fang, J. (2012). Learning intelligent genetic algorithms using Japanese nonograms. IEEE Trans. Education, 55(2), 164–168. doi:10.1109/TE.2011.2158214.

15.

Ueda, N. & Nagao, T. (1996). NP-completeness results for nonogram via parsimonious reductions. Dept. Comput. Sci., Tokyo Inst. Technol., Tokyo, Japan, Tech. Rep. TR96-0008.

16.

Wiggers, W.A. (2004). A comparison of a genetic algorithm and a depth first search algorithm applied to Japanese nonograms. In Twente Student Conf. IT (pp. 1–6).

17.

Wolter, J. (2012). The ‘Pbnsolve’ paint-by-number puzzle solver. Retrieved March 31, 2018, from http://webpbn.com/pbnsolve.html.

18.

Wu, I.C. (2015). Introduction to Nonogram Program Developed at CGI Lab. Retrieved March 31, 2018, from http://aigames.nctu.edu.tw/~icwu/aigames/LalaFrogKK.html.

19.

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 Trans. Computational Intelligence and AI in Games, 5(3), 251–264. doi:10.1109/TCIAIG.2013.2251884.

20.

Yu, C.H., Lee, H.L. & Chen, L.H. (2009). An efficient algorithm for solving nonograms. Appl. Intell., 35(1), 18–31. doi:10.1007/s10489-009-0200-0.