Solving Paint-by-Numbers Puzzles with Integer Programming

by Robert Bosch

The Article

Here is a postscript file pbn.ps of the "Painting by Numbers" installment of Optima Mindsharpener (Optima 65).

The Code

The program pbn.c reads a file pbn.dat (which contains a description of a paint-by-numbers puzzle) and then constructs a file pbn.lp (which describes an integer program that can be solved, with CPLEX, to obtain the solution to the puzzle).

Data Files

The following files describe the paint-by-numbers puzzles that appear in the article:

spaceman.dat : The spaceman puzzle displayed in Figure 1.
dragonfly.dat : The puzzle displayed in Figure 5.

Instructions

To construct a CPLEX ".lp" file for the spaceman puzzle, copy the file spaceman.dat into the (initially nonexistent) file pbn.dat. Then compile the program pbn.c. When you run the program, it will read the file pbn.dat and construct a file pbn.lp.

If you have comments or questions, please e-mail bobb@cs.oberlin.edu

Link to Bob Bosch's page.