On Solving Simple Curved Nonograms
Journal:
arXiv
Published Date:
May 2, 2025
Abstract
Nonograms are a popular type of puzzle, where an arrangement of curves in the
plane (in the classic version, a rectangular grid) is given together with a
series of hints, indicating which cells of the subdivision are to be colored.
The colored cells yield an image. Curved nonograms use a curve arrangement
rather than a grid, leading to a closer approximation of an arbitrary solution
image. While there is a considerable amount of previous work on the natural
question of the hardness of solving a classic nonogram, research on curved
nonograms has so far focused on their creation, which is already highly
non-trivial. We address this gap by providing algorithmic and hardness results
for curved nonograms of varying complexity.
