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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Solving Nonograms: A Constraint Satisfaction Approach

  • Abik Aramian,
  • Varduhi Yeghiazaryan

摘要

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.