Solving Nonograms Using Integer Programming Without Coloring
Author:
- 9 November 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Games
- Vol. 14 (1) , 56-63
Abstract
A new integer linear programming (ILP) formulation is presented for nonogram/crucipixel/paint-by-number puzzles, which involve coloring cells in a grid according to provided clues about how many cells in each row and column ought to be colored. Compared to prior ILP formulations, this new formulation involves far fewer constraints and decision variables. This new formulation was implemented in GAMS; this implementation was found in many instances to approximately halve the CPU time required to identify a solution compared to prior ILP-based approaches. Multicolored nonograms are also permitted in this formulation. Counterintuitively, the new formulation does not make direct reference to cell colors at all, unlike typical by-hand approaches for solving simple instances. A new method is also presented to check uniqueness of a nonogram solution, again without direct reference to cell colors, by employing a result by Besicovitch concerning integer linear independence.Keywords
This publication has 8 references indexed in Scilit:
- Design and Automated Generation of Japanese Picture PuzzlesComputer Graphics Forum, 2019
- Nonograms: Combinatorial questions and algorithmsDiscrete Applied Mathematics, 2014
- Integer Programming2014
- An Efficient Approach to Solving NonogramsIEEE Transactions on Computational Intelligence and AI in Games, 2013
- Solving Nonograms by combining relaxationsPattern Recognition, 2009
- Colored Nonograms: An Integer Linear Programming Approach2009
- Integer sets with distinct subset-sumsMathematics of Computation, 1988
- On the Linear Independence of Fractional Powers of IntegersJournal of the London Mathematical Society, 1940