Solving Nonograms Using Integer Programming Without Coloring

In this article, 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 the modeling language 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 the uniqueness of a nonogram solution, again without direct reference to cell colors, by employing a result by Besicovitch concerning integer linear independence.