Wednesday, April 14, 2010

Nonograms / Paint by Numbers / Griddlers

Nonograms / Paint by Numbers / Griddlers are "picture logic puzzles in which cells in a grid have to be colored or left blank according to numbers given at the side of the grid to reveal a hidden picture. In this puzzle type, the numbers measure how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of "4 8 3" would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive groups." [1]

Simon Tatham's Portable Puzzle Collection has an excellent implementation of these puzzles, under the name "Pattern". They run under Windows, OS X, Linux, and as a Java applet in a browser.

As usual, the powerful answer set solver clingo makes short work of these puzzles. The source files are:
  • nonogram.lp (clingo input file describing the nonogram puzzle type)
  • 10x10.lp (lists the constraints in the above 10x10 puzzle)
  • display (Perl program to display the solution in human-readable form and check its validity against the original constraints)
In this model of the puzzle, the objective is to find the cell in which each unbroken line of filled-in squares ("run") starts, subject to the following constraints:
  • Two runs in the same row or column must be separated by at least one cell of whitespace
  • From the starting cells and lengths of the runs in a row or column, we can infer which cells in that row or column must be filled in. The set of cells filled in by the row runs must be the same as the set of cells filled in by the column runs.
Here's the output of solving the above 10x10 puzzle:
$ clingo nonogram.lp 10x10.lp | perl display
Answer: 1
X X X . .   . . . . . 
. . X . .   . . . . . 
. . . . .   . . X X X 
. . . . .   . . X . X 
X . X . X   X . X . . 

X . X X X   X X X . X 
. . X X X   X . X . X 
X . X X X   X X X . X 
X X X X X   X X X . . 
X X . . X   X X X . . 
OK
SATISFIABLE

Models      : 1+    
Time        : 0.020
  Prepare   : 0.010
  Prepro.   : 0.010
  Solving   : 0.000
Here's the output from solving a 30x30 puzzle, along with an image of the initial puzzle state and the corresponding Simon Tatham's Portable Puzzle Collection save file.

[1] Wikipedia, Nonogram, (as of Apr. 14, 2010, 08:56 GMT).

No comments:

Post a Comment

Followers

Contributors