{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T03:44:52Z","timestamp":1777693492001,"version":"3.51.4"},"reference-count":13,"publisher":"SAGE Publications","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ICG"],"published-print":{"date-parts":[[2019,3,25]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3233\/icg-180069","type":"journal-article","created":{"date-parts":[[2018,11,23]],"date-time":"2018-11-23T10:47:17Z","timestamp":1542970037000},"page":"397-405","source":"Crossref","is-referenced-by-count":1,"title":["Exploring effects of fully probing sequence on solving nonogram puzzles"],"prefix":"10.1177","volume":"40","author":[{"given":"Kuo-Chan","family":"Huang","sequence":"first","affiliation":[{"name":"National Taichung University of Education, Taiwan"}]},{"given":"Jia-Jun","family":"Yeh","sequence":"additional","affiliation":[{"name":"National Taichung University of Education, Taiwan"}]},{"given":"Wei-Chiao","family":"Huang","sequence":"additional","affiliation":[{"name":"National Taichung University of Education, Taiwan"}]},{"given":"Yan-Rong","family":"Guo","sequence":"additional","affiliation":[{"name":"National Taichung University of Education, Taiwan"}]},{"given":"Lung-Pin","family":"Chen","sequence":"additional","affiliation":[{"name":"Tunghai University, Taiwan"}]}],"member":"179","reference":[{"issue":"2","key":"10.3233\/ICG-180069_ref1","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s10851-006-9798-2","article-title":"A network flow algorithm for reconstructing binary images from discrete X-rays","volume":"27","author":"Batenburg","year":"2007","journal-title":"J. Math. Imag. Vis."},{"key":"10.3233\/ICG-180069_ref2","first-page":"1","article-title":"Constructing simple nonograms of varying difficulty","volume":"20","author":"Batenburg","year":"2009","journal-title":"Pure Math. Appl."},{"issue":"8","key":"10.3233\/ICG-180069_ref3","doi-asserted-by":"publisher","first-page":"1672","DOI":"10.1016\/j.patcog.2008.12.003","article-title":"Solving nonograms by combining relaxations","volume":"42","author":"Batenburg","year":"2009","journal-title":"Pattern Recognit."},{"key":"10.3233\/ICG-180069_ref4","first-page":"16","article-title":"Painting by numbers","volume":"65","author":"Bosch","year":"2001","journal-title":"Optima"},{"key":"10.3233\/ICG-180069_ref6","unstructured":"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\u20132967)."},{"key":"10.3233\/ICG-180069_ref7","unstructured":"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\u2013214). Basingstoke, U.K.: Palgrave."},{"issue":"1","key":"10.3233\/ICG-180069_ref8","first-page":"51","article-title":"The 2011 TAAI computer-game tournaments","volume":"34","author":"Lin","year":"2011","journal-title":"Int. Comput. Games Assoc. J."},{"issue":"3","key":"10.3233\/ICG-180069_ref12","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/s10489-011-0335-7","article-title":"Solving Japanese nonograms by Taguchi-based genetic algorithm","volume":"37","author":"Tsai","year":"2012","journal-title":"Appl. Intell."},{"key":"10.3233\/ICG-180069_ref13","doi-asserted-by":"crossref","unstructured":"Tsai, J. & Chou, P. (2011). Solving Japanese puzzles by genetic algorithms. In International Conference on Machine Learning and Cybernetics (pp. 785\u2013788).","DOI":"10.1109\/ICMLC.2011.6016787"},{"issue":"2","key":"10.3233\/ICG-180069_ref14","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1109\/TE.2011.2158214","article-title":"Learning intelligent genetic algorithms using Japanese nonograms","volume":"55","author":"Tsai","year":"2012","journal-title":"IEEE Trans. Education"},{"key":"10.3233\/ICG-180069_ref16","unstructured":"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\u20136)."},{"issue":"3","key":"10.3233\/ICG-180069_ref19","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1109\/TCIAIG.2013.2251884","article-title":"An efficient approach to solving nonograms","volume":"5","author":"Wu","year":"2013","journal-title":"IEEE Trans. Computational Intelligence and AI in Games"},{"issue":"1","key":"10.3233\/ICG-180069_ref20","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/s10489-009-0200-0","article-title":"An efficient algorithm for solving nonograms","volume":"35","author":"Yu","year":"2009","journal-title":"Appl. Intell."}],"container-title":["ICGA Journal"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/ICG-180069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:12:54Z","timestamp":1777453974000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/ICG-180069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,25]]},"references-count":13,"journal-issue":{"issue":"4"},"URL":"https:\/\/doi.org\/10.3233\/icg-180069","relation":{},"ISSN":["2468-2438","1389-6911"],"issn-type":[{"value":"2468-2438","type":"electronic"},{"value":"1389-6911","type":"print"}],"subject":[],"published":{"date-parts":[[2019,3,25]]}}}