Utilize este identificador para referenciar este registo: http://hdl.handle.net/10362/2388
Título: Solving colored nonograms
Autor: Mingote, Luís Pedro Canas Ferreira
Orientador: Azevedo, Francisco
Palavras-chave: Nonogram
Integer linear programming
Data de Defesa: 2009
Editora: FCT - UNL
Resumo: 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.
Descrição: Trabalho apresentado no âmbito do Mestrado em Engenharia Informática, como requisito parcial para obtenção do grau de Mestre em Engenharia Informática
URI: http://hdl.handle.net/10362/2388
Aparece nas colecções:FCT: DI - Dissertações de Mestrado

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
Mingote_2009.pdf2,18 MBAdobe PDFVer/Abrir

FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.