| Title: |
On Solving Simple Curved Nonograms |
| Authors: |
Löffler, Maarten; Rote, Günter; Terziadis, Soeren; Weinberger, Alexandra; Sub Geometric Computing; Fernau, Henning; Zhu, Binhai |
| Publication Year: |
2025 |
| Subject Terms: |
Arrangement; Dynamic Programming; Nonogram; Puzzle; Taverne; Theoretical Computer Science; General Computer Science |
| Description: |
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. |
| Document Type: |
book part |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
0302-9743 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/483022 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/483022 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.C7B48BE3 |
| Database: |
BASE |