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
• Document Type: Master thesis
• Language: English
• Advisor(s): Azevedo, Francisco
• Contributor(s): RUN

Description

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

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.