Solving Nonograms: A Constraint Satisfaction Approach
摘要
This paper explores automated Nonogram solving using a constraint satisfaction problem (CSP) formulation. Nonograms require players to use numerical clues to color cells in a grid and reveal a hidden image. Our approach decomposes the puzzle into separate CSPs for each row and column, where the starting positions of clues are treated as variables, with constraints ensuring non-overlapping and sufficient spacing. Once these individual CSPs are solved, the entire puzzle board is modeled as a single CSP, with rows and columns as variables and constraints enforcing cell color consistency at intersections. To efficiently solve the puzzle, we employ inference and backtracking techniques, enhanced by Nonogram-specific logical analysis. We conduct comparative analyses with established solving methods to evaluate the effectiveness of our proposed approach. Experimental results demonstrate the efficiency of our CSP formulation and automated solving algorithm.