On Efficiency of Fully Probing Mechanisms in Nonogram Solving Algorithm.

Fully probing plays an important role in the nonogram solving algorithm developed by Wu et al., whose implementation, named LalaFrogKK, has won several nonogram tournaments since 2011. Different fully probing methods affect the overall nonogram solving performance greatly as shown in previous studies. In this paper, we explore fully probing efficiency from different aspects and evaluate its impact on the performance of solving an entire nonogram puzzle. In the exploration, we found several critical factors influencing fully probing efficiency greatly, i.e. re-probing policy, probing sequence, and computational overhead. Taking these critical factors in account, we developed several new fully probing mechanisms to improve nonogram solving performance. Experimental results based on the puzzles of previous nonogram tournaments show that our new fully probing methods have the potential to improve the speed of solving nonogram puzzles significantly.