Document details

Solving colored nonograms

Author(s): Mingote, Luís Pedro Canas Ferreira

Date: 2009

Persistent ID: http://hdl.handle.net/10362/2388

Origin: Repositório Institucional da UNL

Subject(s): Nonogram; Paint-by-numbers; ILP; Integer linear programming


Description

In this thesis we deepen the study of colored nonogram solving using Integer Linear Programming(ILP). The known methods for solving this kind of problems are the depth-first search(brute-force) one, the iterative one and the ILP one. Our approach generalizes the one used by Robert A. Bosch which was developed for black and white nonograms only, thus providing a new universal solution for solving nonograms using ILP. Since the iterative implementations are the ones that present better performance results, we also developed a hybrid method that combines this approach and the ILP one. These puzzles often have more than one solution. The way to find them using the iterative method is to make a tree search with backtracking. In order to find the remaining solutions using our approach, it is necessary to apply an algorithm that uses a binary cut to exclude already known solutions. In order to perform comparative tests between approaches, we developed a nonogram generator that allows us to define the resolution of the puzzle, its number of colors and its density(number of painted cells vs. resolution). Finally we compare the performance of our approach in solving colored nonograms against the iterative one.

Trabalho apresentado no âmbito do Mestrado em Engenharia Informática, como requisito parcial para obtenção do grau de Mestre em Engenharia Informática

Document Type Master thesis
Language English
Advisor(s) Azevedo, Francisco
Contributor(s) Mingote, Luís Pedro Canas Ferreira
facebook logo  linkedin logo  twitter logo 
mendeley logo

Related documents

No related documents