A Reasoning Framework for Solving Nonograms
Nonograms, also known as Japanese puzzles, are logic puzzles that are sold by many news paper vendors. 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 co
- PDF / 250,369 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 95 Downloads / 230 Views
2
Vision Lab, Department of Physics University of Antwerp, Belgium [email protected] Leiden Institute of Advanced Computer Science Leiden University, The Netherlands [email protected]
Abstract. Nonograms, also known as Japanese puzzles, are logic puzzles that are sold by many news paper vendors. 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 local reasoning framework that can be used to deduce the value of certain pixels in the puzzle, given a partial filling. By iterating this procedure, starting from an empty grid, it is often possible to solve the puzzle completely. Our approach is based on ideas from dynamic programming, 2-satisfiability problems, and network flows. 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. Moreover, all the computations involved in the solution process can be performed in polynomial time.
1
Introduction
A Nonogram, also known as a Japanese puzzle in some countries, is a kind of logic puzzle, where the goal is to draw a rectangular image that adheres to certain row and column constraints. Usually, the image is black-and-white, although Nonograms with more than two grey values exist as well. Fig. 1 shows an example of a Nonogram. The puzzle has a rectangular shape, which is subdivided in unit cells. We will also refer to these cells as pixels. For each row and each column, a description is given. The description indicates the length of the consecutive segments of black pixels along the corresponding line. For example, the description “1, 1” in the first row indicates that when traversing the pixels in that row from left to right, there should first be zero or more white pixels, followed by one black pixel. Then, at least one white pixel must occur, followed by exactly one black pixel. There may be additional white pixels at the end of the line. The symbol denotes the empty description, leading to an all white line. The goal V.E. Brimkov, R.P. Barneva, H.A. Hauptman (Eds.): IWCIA 2008, LNCS 4958, pp. 372–383, 2008. c Springer-Verlag Berlin Heidelberg 2008
A Reasoning Framework for Solving Nonograms
373
1 1, 1 1 1, 1 1 1, 1
0
1
0
1
0
0
0
0
0
0
1, 1
x
x
0
x
x
3
x
x
1
x
x
t
t
t
t t
t
t
Fig. 1. A simple 4×5 Nonogram: a) original puzzle; b) partial solution (1 = black, 0 = white, x = yet unknown); c) final solution (dots denote black pixels)
of the puzzle is to colour all pixels with either black or white, in such a way that each horizontal and vertical line is consistent with the given description. As we shall see later, when using only information concerning single rows an
Data Loading...
