Affiliations: [a] National Taichung University of Education, Taiwan | [b] Tunghai University, Taiwan
Correspondence:
[*]
Corresponding author. No.140, Minsheng Rd., West Dist., Taichung City 40306, Taiwan. Tel.: +886-4-22183813; Fax: +886-4-22183580; E-mail: kchuang@mail.ntcu.edu.tw.
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.
