A carregar...
Publicação
Solving colored nonograms
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 2.12 MB | Adobe PDF |
Orientador(es)
Resumo(s)
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
Palavras-chave
Nonogram Paint-by-numbers ILP Integer linear programming