Sage Journals: Discover world-class research

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

Get full access to this article

View all access options for this article.

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.

Exploring effects of fully probing sequence on solving nonogram puzzles

Abstract

Keywords

Get full access to this article

References