Premium
Design and Automated Generation of Japanese Picture Puzzles
Author(s) -
van de Kerkhof Mees,
de Jong Tim,
Parment Raphael,
Löffler Maarten,
Vaxman Amir,
van Kreveld Marc
Publication year - 2019
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/cgf.13642
Subject(s) - subdivision , computer science , grid , bounded function , convergence (economics) , simulated annealing , square tiling , extension (predicate logic) , computer graphics (images) , algorithm , theoretical computer science , mathematical optimization , geometry , mathematics , programming language , mathematical analysis , archaeology , economics , history , economic growth
We introduce the generalized nonogram, an extension of the well‐known nonogram or Japanese picture puzzle. It is not based on a regular square grid but on a subdivision (arrangement) with differently shaped cells, bounded by straight lines or curves. To generate a good, clear puzzle from a filled line drawing, the arrangement that is formed for the puzzle must meet a number of criteria. Some of these relate to the puzzle and some to the geometry. We give an overview of these criteria and show that a puzzle can be generated by an optimization method like simulated annealing. Experimentally, we analyze the convergence of the method and the remaining penalty score on several input pictures along with various other design options.