Japanese Puzzles / Curved Nonagrams

This is ongoing work that started during a Dagstuhl seminar on geometric and topological reconfiguration, with Hsien-Chih Chang, Maarten Löffler, Tim Ophelders and Lena Schlipf. Nonograms, also known as Japanese puzzles, paint-by-numbers, or griddlers, are a popular puzzle type where one is given an empty grid and a set of clues on which grid cells need to be colored. A clue consists of a sequence of numbers specifying the numbers of consecutive filled cells in a row or column. Van de Kerkhof et al. introduced curved nonograms, a variant in which the puzzle is no longer played on a grid but on any arrangement of curves. Maarten realised that the difficulty of these puzzles could be boiled down to self intersecting curves and to the notion of popular face, a region in the puzzle whose boundary is visited multiple times by the same curve at different spots. We then showed that the problem of modulating the difficulty of a puzzle by removing these popular faces or self intersections using a natural local de-entangling operation of the curves where they intersect is NP-hard.