A fast nonogram solver that won the TAAI 2017 and ICGA 2018 tournaments

Article type: Research Article

Authors: Chen, Yen-Chi | Lin, Shun-Shii^{; *}

Affiliations: Department of CSIE, National Taiwan Normal University, Taipei, Taiwan, ROC

Correspondence: [*] Corresponding author. E-mail: linss@csie.ntnu.edu.tw.

Abstract: A nonogram is a pen and paper single-player logic game in which players paint each cell of a two-dimensional grid according to clues for specific rows and columns. This paper improves on the method proposed by Wu et al. by adding a freedom parameter which can significantly reduce the total computation cost of maximal painting. Combining a well-designed bitboard with BMI instructions in the CPU, we reduce memory loading while accelerating operations. Our Nonogram program, named Requiem, solved all 1000 puzzles in every Nonogram Tournament from 2011 to 2018 faster than all previous medal programs. Furthermore, we beat four other teams to win the TAAI 2017 Tournament, six other teams to win the ICGA 2018 Tournament and three other teams to win the TAAI 2018. To our knowledge, Requiem offers the best puzzle solving performance at the present time.

Keywords: Nonogram, bitboard, puzzle, dynamic programming, BMI

DOI: 10.3233/ICG-190097

Journal: ICGA Journal, vol. 41, no. 1, pp. 2-14, 2019