Detalhes do Documento

Solving colored nonograms

Autor(es): Mingote, Luís Pedro Canas Ferreira

Data: 2009

Identificador Persistente: http://hdl.handle.net/10362/2388

Origem: Repositório Institucional da UNL

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


Descrição

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

Tipo de Documento Dissertação de mestrado
Idioma Inglês
Orientador(es) Azevedo, Francisco
Contribuidor(es) Mingote, Luís Pedro Canas Ferreira
facebook logo  linkedin logo  twitter logo 
mendeley logo

Documentos Relacionados

Não existem documentos relacionados.