Labeling Curved Nonograms

Abstract

In this thesis we compare 4 algorithms that solve the problem of labeling curved nonograms. A curved nonogram is a variation of the classic nonogram a type of logic pen-and-paper puzzle, sometimes called a japanese puzzle. Unlike classic nonograms, in a curved nonogram the clues are not shown in a uniform grid, but as labels attached to the puzzle boundary. The discussed algorithms attempt to find a valid minimum-length labeling, that is a set of placed labels where no two labels overlap with each other, and the total extension length (distance between the attachment point and the label) is minimized.