Publication
Title
Solving Nonograms by combining relaxations
Author
Abstract
Nonograms, also known as Japanese puzzles, are a specific type of logic drawing puzzles. The challenge is to fill a grid with black and white pixels in such a way that a given description for each row and column, indicating the lengths of consecutive segments of black pixels, is adhered to. Although the Nonograms in puzzle books can usually be solved by hand, the general problem of solving Nonograms is NP-hard. In this paper, we propose a reasoning framework that can be used to determine the value of certain pixels in the puzzle, given a partial filling. Constraints obtained from relaxations of the Nonogram problem are combined into a 2-Satisfiability (2-SAT) problem, which is used to deduce pixel values in the Nonogram solution. By iterating this procedure, starting from an empty grid, it is often possible to solve the puzzle completely. All the computations involved in the solution process can be performed in polynomial time. Our experimental results demonstrate that the approach is capable of solving a variety of Nonograms that cannot be solved by simple logic reasoning within individual rows and columns, without resorting to branching operations. In addition, we present statistical results on the solvability of Nonograms, obtained by applying our method to a large number of Nonograms.
Language
English
Source (journal)
Pattern recognition. - Oxford
Publication
Oxford : 2009
ISSN
0031-3203
Volume/pages
42:8(2009), p. 1672-1683
ISI
000266183800006
Full text (Publisher's DOI)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identification
Creation 06.08.2009
Last edited 16.09.2017
To cite this reference