Complexity and solvability of Nonogram puzzles

Oosterman, R.A. (2017) Complexity and solvability of Nonogram puzzles. Master's Thesis / Essay, Science Education and Communication.

Preview	Text Master_Educatie_2017_RAOosterman.pdf - Published Version Download (3MB) | Preview
	Text toestemming.pdf - Other Restricted to Backend only Download (79kB)

Abstract

Nonograms (Japanese puzzles) are popular in both Japan and the Netherlands. The purpose is to colour multiple pixels on a grid to obtain a picture. Based on numbers corresponding to each row and column of the grid, we can derive which sequences of black pixels need to be coloured, in order to obtain the eventual picture. Solving such a puzzle can be seen as a special case of discrete tomography. The existence and uniqueness of the solution of a Nonogram can be approached mathematically. During the presentation, we will give an introduction to complexity theory, and the satisfiability (SAT) problems in particular. This will form the basis of the research, as we can derive the complexity of both the solving and uniqueness problems from this. Via parsimonious reduction to 3-SAT, we can show that both problems belong to the complexity class NP-complete. After having treated the theoretical complexity of Nonograms, we take a look at how these puzzles can be solved. Since the existence of a solution is NP-complete, it is not immediately obvious how to obtain a solution. We propose several heuristic solving steps to see whether we can determine several pixel values in a row or column, based on specific properties of its description. Furthermore, we compare the functionality of some already existing solvers by applying several examples of Nonogram puzzles. These are applied to cases where a unique solution is known to exist, and also to cases where the solution is not unique.

Item Type:	Thesis (Master's Thesis / Essay)
Degree programme:	Science Education and Communication
Thesis type:	Master's Thesis / Essay
Language:	English
Date Deposited:	15 Feb 2018 08:28
Last Modified:	15 Feb 2018 08:28
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/15287

Actions (login required)

View Item