Solving simple curved nonograms
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.
Authors
- Alexandra Weinberger (ORCID: https://orcid.org/0000-0001-8553-6661)
- Soeren Terziadis (ORCID: https://orcid.org/0000-0001-5161-3841)
- Günter Rote (ORCID: https://orcid.org/0000-0002-0351-5945)
- Maarten Löffler (ORCID: https://orcid.org/0009-0001-9403-8856)
Institutions
- FernUniversität in Hagen (DE)
- Utrecht University (NL)
- Technical University of Munich (DE)
- Freie Universität Berlin (DE)
Publication Details
- Journal
- Acta Informatica
- Published
- 2026-11-19
- DOI
- https://doi.org/10.1007/s00236-026-00536-z
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00