How to Play Sprouts with Playing Cards

It's not much fun to play sprouts with playing cards, but it is possible. Why would anyone want to do such a thing? Maybe it will be easier to analyze the game or more straightforward to implement it on a computer this way. Maybe you're fresh out of pens and paper.

To play a game with N initial spots, you'll need three identical decks of playing cards with at least 3N+1 distinct cards in each deck. This way each card will have exactly two identical "twins". (Actually, the cards are incidental; integers will suffice. This document is really about how to generate legal moves and update a position represented in Dan Hoey's boundary-list notation.) In the rules below, we'll assume you've combined the three decks into one large deck. You will also need a flat space for at least 2N+1 rows of cards. A large wooden table will do nicely. Each row will contain zero or more stacks of cards, and each stack will contain one or more cards.

To "cut" a stack of cards means the usual thing: remove one or more cards from the top of the stack (preserving order) and put them under the remaining cards in the stack. Here, the player may examine the stack and cut it in any place they choose.

To "play" a card, remove it from the deck and place it in the specified location.

Initial position and play

The initial position consists of N different cards, each in an isolated stack, all in the same row. Players take turns moving. There are two kinds of moves, joining moves and dividing moves. On his turn, a player must execute either a legal joining move or a legal dividing move, but not both in the same turn. Under the normal play convention, the last player wins. Under the misere play convention, the last player loses.

Joining moves

A joining move combines two stacks in the same row. If any step of the move is not possible, the move is illegal.

1. Choose two different nonempty stacks A and B in the same row. Optionally, cut stack A. Optionally, cut stack B.
2. If A has more than one card, then play a twin of the top card to the bottom of the stack.
3. If B has more than one card, then play a twin of the top card to the bottom of the stack.
4. From the deck, remove two identical cards that are not already on the table. Place one on top of A, and one on top of B.
5. Place A on top of B.

Dividing moves

A dividing move divides a stack into two stacks, one of which is placed in a new row. One or more stacks from the original row may be moved to the new row. If any step of the move is not possible, the move is illegal.

1. Choose a nonempty stack. Optionally, cut it.
2. Play a twin of the top card to the bottom of the stack.
3. Remove one or more cards -- but not all of them -- from the top of the stack and place them in a new row.
4. If the original stack or the new stack has more than one card, then play a twin of the the bottom card of the new stack to the top of the original stack.
5. From the deck, remove two identical cards that are not already on the table. Place one on top of the new stack, and one on top of the original stack.
6. Optionally, move one or more stacks -- other than the original stack — from the original row to the new row.

Example game

Consider the following game of 5 moves (in WGOSA notation): 2+ 1(3)2 1(4)2 1(5)4 2(6)3 (see images below)

Here's how that game would be played with cards. To represent the position in text, we will use the following conventions: A stack of cards is written in order from top card to bottom, with a comma between each card. A semicolon separates each stack from adjacent stacks in the same row. A slash separates each row from its neighbors. (This is the notation used by Dan Hoey in his paper on sprouts notation.)

(2)	initial position:	1;2
(3)	joining move:	1;2 (skipped) (skipped) 1,3;2,3 1,3,2,3
(4)	dividing move:	1,3,2,3 1,3,2,3,1 1,3,2/3,1 1,3,2/2,3,1 4,1,3,2/4,2,3,1 (skipped)
(5)	dividing move:	1,3,2,4/4,2,3,1 1,3,2,4,1/4,2,3,1 1,3,2,4/1/4,2,3,1 1,3,2,4/4,1/4,2,3,1 5,1,3,2,4/5,4,1/4,2,3,1 (skipped)
(6)	dividing move:	5,1,3,2,4/5,4,1/2,3,1,4 5,1,3,2,4/5,4,1/2,3,1,4,2 5,1,3,2,4/5,4,1/2,3/1,4,2 5,1,3,2,4/5,4,1/2,3/3,1,4,2 5,1,3,2,4/5,4,1/6,2,3/6,3,1,4,2 (skipped)

Analogy with graph

We have represented a plane graph using rows of stacks of cards.

Playing card term	≈	Graph theory term
card	≈	occurrence of vertex in boundary
stack	≈	left-hand walk of vertices on boundary
row	≈	face, i.e. set of boundaries
table	≈	plane graph, i.e. set of faces

Credits

Author: Josh Jordan
Initially published at http://www.wgosa.org/playingcardssprouts.htm

This document builds upon the sprouts notation system devised by Dan Hoey.

John Graham-Cunning's Minimum Coin Problems

In The Minimum Coin Problem, John Graham-Cunning poses the following problems:

1. Given a pile of coins and a target amount, find a way to pay exactly that amount using the maximum number of coins from the pile.
2. Given a pile of coins and a target amount, find a way to pay at least that amount using the maximum number of coins from the pile, such that removing any coin from the payment yields an amount that is less than the target amount.
3. Given a pile of coins — each type of coin having a given weight — and a target amount, find a way to pay at least that amount using the maximum weight of coins from the pile, such that removing any coin from the payment yields an amount that is less than the target amount.

These can each be posed as integer programming problems and solved with a solver such as GLPK. Here is a solution to problem 1, a solution to problem 2, and a solution to problem 3.

Open-source answer set solver vs Fico Xpress Optimization Suite

Fico's Xpress Optimization Suite is used by American Airlines, Avis, Honeywell, and the NFL to solve industrial-sized problems in operations research. I was reading one of Fico's white papers, Hybrid MIP/CP solving with Xpress-Optimizer and Xpress-Kalis (May, 2009), when I came across the following statement about a problem in machine assignment and sequencing.

"It is possible to implement this problem entirely either with Xpress-Optimizer or wit Xpress-Kalis. However, already for this three machines – 12 jobs instance the problem is extremely hard for either technique on its own." [Section 3.4 ("Results"), page 19, italics mine]

Fico approached this dilemma by creating a hybrid of the solutions for both solvers. The code looked complicated, though, and the problem itself didn't seem that hard. I wanted to see if I was missing something, so I wrote it up in the language of the open-source answer-set solver Clingo.
According to the paper, "Optimality is proven within a few seconds on a Pentium IV PC." It takes clingo 3.5 seconds on an Athlon 64 (a similar CPU) to find the same solution. The Xpress-Optimizer+Xpress-Kalis hybrid solution is about 220 lines of code (LOC), while the Clingo solution is about 20 LOC. (*)

#const maxtime = 39.
machine(1..3).
product(1..12).

% table2(P,T1,T2,T3,D1,D2,D3,S,E) :- product P costs C1,C2,and C3 and takes D1,D2,D3
%     duration on machines 1,2,3, and must start on or after time S, and must end before time E.

table2(1,12,6,7,10,14,13,2,32).
table2(2,13,6,10,7,9,8,4,33).
table2(3,10,4,6,11,17,15,5,36).
table2(4,8,4,5,6,9,12,7,37).
table2(5,12,6,7,4,6,10,9,39).
table2(6,10,5,6,2,3,4,0,34).
table2(7,7,4,5,10,15,16,3,30).
table2(8,9,5,5,8,11,12,6,26).
table2(9,10,5,7,10,14,13,11,36).
table2(10,8,4,5,8,11,14,2,38).
table2(11,15,8,9,9,12,16,3,31).
table2(12,13,7,7,3,5,6,4,22).
cost(P,1,C1) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
cost(P,2,C2) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
cost(P,3,C3) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
dur(P,1,D1) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
dur(P,2,D2) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
dur(P,3,D3) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
legalworktime(P,S..E-1) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).

% machine(P,M). We choose to build product P on machine M.
% start(P,T). We choose to start building product P at time T.

% Each product is built on exactly one machine.
1 { machine(P, M) : machine(M) } 1 :- product(P).

% Each product starts at exactly one time.
1 { start(P, S) : legalworktime(P,S)  } 1 :- product(P).

% machinetime(P,M,T) :- machine is working on product P at time T.
machinetime(P,M,S..S+D-1) :- start(P,S), machine(P,M), dur(P,M,D).

% machinetime(P,T) :- product P is being worked on at time T.
machinetime(P,T) :- machinetime(P,M,T).

:- machinetime(P,M,T), machinetime(Q,M,T), P != Q.
:- machinetime(P,T), not legalworktime(P,T).

% run(P,M,S,E) :- machine is building P at times T, where S ≤ T < E.
% (used only for output)
run(P,M,S,S+D) :- product(P), machine(P,M), start(P,S), dur(P,M,D).
#hide.
#show run/4.
#show cost/1.

% cost(P,C). product P costs $C, given the machine we are making it on
cost(P,C) :- machine(P,M), cost(P,M,C).
totalcost(Cost) :- Cost = #sum [cost(P,C) : product(P) = C].

#minimize [totalcost(Cost) = Cost].

According to Section 4 (Summary), "Hybrid solution algorithms need to be developed, implemented, and tested on a case-by-case basis, meaning a considerable investment in terms of development effort and requiring a good understanding of the solution methods and solvers involved."

Indeed. Or you could just use Clingo.


(*)  When counting LOC, I ignored lines that consisted only of

• comments,
• code for displaying output,
• code for specifying the problem parameters (there were none of these in the Xpress solution), or
• code for configuring the solver (there were none of these in the clingo solution).

How I Beat the World Champion at Sprouts

With the help of my program Aunt Beast, I won the World Game of Sprouts Association 2010-2011 Tournament in January, 2011. The human world champion requested a follow-up match, billed by WGOSA as the “2011 Clash of the Titans” . As of March, 2011, the match is still ongoing, but in mid-February, I won the first game. Here’s how I did it.

Update I: I also won game 2. Here's my analysis.

Update II: I lost game 3, but won game 4. Analysis forthcoming.
Update III: I won game 5 and lost game 6, so I won the match. WGOSA has a write-up.

FlowerFinder by William Waite

FlowerFinder is a puzzle with only 6 pieces but a rather large state space. One objective is to place them into the frame in two layers so that in each of the 9 circles, exactly 3 petals are visible.

Each circle can be one of four types, which we will call "top-left", "top-right", "bottom-left", and "bottom-right". We will assign each piece a number from 1 to 6. Each piece is defined as a sequence of three circle types. For example, in the photo, the circles in piece 1, from top to bottom, are of type down-left, up-right, and up-left. Before a piece is placed in the frame, it can (optionally) be flipped horizontally and (optionally) be flipped vertically. We define locations 1,2,3 as the bottom of the frame from left to right, and locations 4,5,6 as the locations in the top of the frame, perpendicular to 1,2,3. Without loss of generality, we can assume that piece 1 is in location 1 or 2, and is not flipped horizontally or vertically. Finally, we require that the petals in each circle in the top row align with the petals in the corresponding circle in the bottom row.

$ clingo 0 flowerfinder.lp
% flowerfinder.lp source

% piece(P) - P is a piece.
% piece(P,A,B,C) - P's circles, in order, are of type A,B, and C.
% piece(P,N,X) - P's Nth circle (1-based) is of type X.
% transform(TransformType,CircleBefore,CircleAfter) - a transformation of
%  TransformType changes a circle of type CircleBefore to one of type
%  CircleAfter
% align(P,N,Q,M) - when all the pieces are in the frame, circle N of piece P
%  aligns with circle M of piece Q.
% fliph(P) - piece P is flipped horizontally before placing it in the frame.
% flipv(P) - piece P is flipped vertically before placing it in the frame.
% fliphed(P,N,X) - after horizontal flipping (if any), the Nth circle of piece P is of type X.
% flipved(P,N,X) - after vertical flipping (if any), the Nth circle of piece P is of type X.
% orientation(P,N,X) - after 90 degree rotation (if any), the Nth circle of piece P is of type X.
% pieceloc(P,L) - piece P is in location L in the frame (1..6).

piece(1..6).
piece(1,downleft,upright,upleft).
piece(2,upright,upleft,upright).
piece(3,downright,upleft,downleft).
piece(4,upright,downleft,upright).
piece(5,downleft,downright,upright).
piece(6,downright,upright,downleft).

piece(P,1,A) :- piece(P,A,B,C).
piece(P,2,B) :- piece(P,A,B,C).
piece(P,3,C) :- piece(P,A,B,C).

transform(fliph,downleft,downright).
transform(fliph,downright,downleft).
transform(fliph,upleft,upright).
transform(fliph,upright,upleft).
transform(flipv,downleft,upleft).
transform(flipv,downright,upright).
transform(flipv,upleft,downleft).
transform(flipv,upright,downright).
transform(rot90,downleft,downright).
transform(rot90,upright,upleft).
transform(rot90,downright,upright).
transform(rot90,upleft,downleft).

align(1,1,4,1).
align(1,2,5,1).
align(1,3,6,1).
align(2,1,4,2).
align(2,2,5,2).
align(2,3,6,2).
align(3,1,4,3).
align(3,2,5,3).
align(3,3,6,3).


% There are as many locations as pieces.
location(P) :- piece(P).

0 { fliph(P) } 1 :- piece(P).
0 { flipv(P) } 1 :- piece(P).
1 { pieceloc(P,L) : location(L) } 1 :- piece(P).

% Without loss of generality, assume piece 1 is in location 1 or 2 (that is,
% on a side or in the middle), and not flipped horizontally or vertically.
:- pieceloc(1, L), L > 2.
:- fliph(1).
:- flipv(1).

% Two different pieces can't be in the same location.
:- pieceloc(P,L),pieceloc(Q,L), P != Q.

% Pieces in locations 4,5,6 are rotated 90 degrees.
rot90(4;5;6).

fliphed(P,N,B) :- piece(P,N,A), transform(fliph,A,B), fliph(P).
fliphed(P,N,A) :- piece(P,N,A), not fliph(P).
flipved(P,4-N,B) :- fliphed(P,N,A), transform(flipv,A,B), flipv(P).
flipved(P,N,A) :- fliphed(P,N,A), not flipv(P).
orientation(P,4-N,B) :- flipved(P,N,A), transform(rot90,A,B), rot90(P).
orientation(P,N,A) :- flipved(P,N,A), not rot90(P).

:- pieceloc(P1,L1), pieceloc(P2,L2), align(L1,C1,L2,C2), orientation(P1,C1,O1), orientation(P2,C2,O2), O1 != O2.


#hide.
#show fliph/1.
#show flipv/1.
#show pieceloc/2.

Answer: 1
fliph(3) fliph(5) fliph(6) flipv(2) flipv(3) pieceloc(1,1) pieceloc(2,2) pieceloc(3,3) pieceloc(4,6) pieceloc(5,4) pieceloc(6,5)
SATISFIABLE

Models      : 1
Time        : 0.020
  Prepare   : 0.010
  Prepro.   : 0.000
  Solving   : 0.010

So the unique solution is to horizontally flip pieces 3, 5, and 6, vertically flip 2 and 3, put the pieces in the specified locations.

How large is the state space? The first piece is in one of two locations, and there are 5! ways to place the remaining pieces, 2⁵ ways to represent the "horizontally flipped" state of those pieces, and 2⁵ ways to represent the "vertically flipped" state of each of those pieces. Finally, the top layer can either be perpendicular to the bottom layer or not. By this reasoning, there are 5! · 2⁵ · 2⁵ · 2 = 257760 different ways to place the 6 pieces in the frame.

Pasquale's Problem

Pasquale is a self-employed machinist who sells two products: P and Q. The market will accept up to 100 Ps and 100 Qs per week. P sells for $200 and Q sells for $195. The raw materials for each part cost $50. It takes him 18.5 minutes to build a P and 16.5 minutes to build a Q. Pasquale's supplier also sells partially-assembled raw materials for P and Q. The partially-assembled raw materials save him 3 minutes per P and 3.5 minutes per Q, but they also cost more: an additional $25 per P and $29 per Q. Given that Pasquale works at most 40 hours per week, what is Pasquale's maximum weekly profit? For simplicity, assume that the quantity of Ps and Qs he produces each week can be specified by a rational number.

Calculators are allowed, but solving this without a computer is quite a challenge.

Here's a hint (rot13): Ubj zhpu jbhyq Cnfdhnyr or noyr gb znxr vs ur qvqa'g unir gur bcgvba bs hfvat cnegvnyyl-nffrzoyrq enj zngrevnyf?

This problem can be solved quite easily with a linear programming solver, such as the one at http://www.zweigmedia.com/RealWorld/simplex.html. Let p and q be the number of Ps and Qs produced each week using only raw materials, and let p' and q' be the number of Ps and Qs produced each week using partially-assembled raw materials.

Maximize z = 150p + 125p'+ 145q + 116q' subject to 
18.5p + 16.5q + 15.5p' + 13q' <= 2400
p + p' <= 100
q + q' <= 100

Optimal Solution: z = 20581.1; p = 40.5405, p' = 0, q = 100, q' = 0

So the most Pasquale can make is $20581.10/week. He can do this by avoiding the partially-assembled raw materials entirely, making as many Qs as the market will accept (100), and spending the remainder of his time on Ps (40.5405).

Click here to view the solution

This puzzle was inspired by a paper by Balakrishnan [1].

[1] Balakrishnan, Jaydeep. The theory of constraints and the make-or-buy decision. Journal of Supply Chain Management, January 1, 2005 .

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)
  

  % constraint(Type,N,I,Len) - the Ith group in row/col N must be Len blocks long
  % row(Y). Y is a valid row number.
  % col(X). X is a valid column number.
  % color(X,Y). From a column constraint, we infer that (X,Y) is colored in
  % rowcolor(X,Y). From a row constraint, we infer that (X,Y) is colored in
  % rowrun(Y,I,X). The Ith run in row Y starts at cell (X,Y).
  % colrun(X,I,Y). The Ith run in col X starts at cell (X,Y).
  
  % This following lines simplifies data entry directly into clingo by allowing
  % constraints to be entered as a group.  This could easily be elminated with
  % some pre-processing in, say, Perl.
  %
  % constraints(col/row,I,A,B,C,...) - The lengths of blocks of filled-in
  %    cells in column/row I are A,B,C,...
  constraint(Type,N,1,A) :- constraints(Type,N,A).
  constraint(Type,N,1,A) :- constraints(Type,N,A,B).
  constraint(Type,N,1,A) :- constraints(Type,N,A,B,C).
  constraint(Type,N,1,A) :- constraints(Type,N,A,B,C,D).
  constraint(Type,N,1,A) :- constraints(Type,N,A,B,C,D,E).
  constraint(Type,N,1,A) :- constraints(Type,N,A,B,C,D,E,F).
  constraint(Type,N,1,A) :- constraints(Type,N,A,B,C,D,E,F,G).
  constraint(Type,N,2,B) :- constraints(Type,N,A,B).
  constraint(Type,N,2,B) :- constraints(Type,N,A,B,C).
  constraint(Type,N,2,B) :- constraints(Type,N,A,B,C,D).
  constraint(Type,N,2,B) :- constraints(Type,N,A,B,C,D,E).
  constraint(Type,N,2,B) :- constraints(Type,N,A,B,C,D,E,F).
  constraint(Type,N,2,B) :- constraints(Type,N,A,B,C,D,E,F,G).
  constraint(Type,N,3,C) :- constraints(Type,N,A,B,C).
  constraint(Type,N,3,C) :- constraints(Type,N,A,B,C,D).
  constraint(Type,N,3,C) :- constraints(Type,N,A,B,C,D,E).
  constraint(Type,N,3,C) :- constraints(Type,N,A,B,C,D,E,F).
  constraint(Type,N,3,C) :- constraints(Type,N,A,B,C,D,E,F,G).
  constraint(Type,N,4,D) :- constraints(Type,N,A,B,C,D).
  constraint(Type,N,4,D) :- constraints(Type,N,A,B,C,D,E).
  constraint(Type,N,4,D) :- constraints(Type,N,A,B,C,D,E,F).
  constraint(Type,N,4,D) :- constraints(Type,N,A,B,C,D,E,F,G).
  constraint(Type,N,5,E) :- constraints(Type,N,A,B,C,D,E).
  constraint(Type,N,5,E) :- constraints(Type,N,A,B,C,D,E,F).
  constraint(Type,N,5,E) :- constraints(Type,N,A,B,C,D,E,F,G).
  constraint(Type,N,6,F) :- constraints(Type,N,A,B,C,D,E,F).
  constraint(Type,N,6,F) :- constraints(Type,N,A,B,C,D,E,F,G).
  constraint(Type,N,7,G) :- constraints(Type,N,A,B,C,D,E,F,G).
  
  
  row(1..ymax).
  col(1..xmax).
  ymax(ymax).
  xmax(xmax).
  % For each constraint, choose a starting cell for the run.
  1 { rowrun(Y,I,X) : col(X) : col(X+Len-1) } 1 :- constraint(row,Y,I,Len).
  1 { colrun(X,I,Y) : row(Y) : row(Y+Len-1) } 1 :- constraint(col,X,I,Len).
  
  % Must leave at least one space between two adjacent run.
  :- rowrun(N,I,Start1), rowrun(N,J,Start2), constraint(row,N,I,Len), I < J, Start2 < Start1 + Len + 1.
  :- colrun(N,I,Start1), colrun(N,J,Start2), constraint(col,N,I,Len), I < J, Start2 < Start1 + Len + 1.
  
  % Infer the color of the cells in each run
  color(X,Start..Start+Len-1) :- colrun(X,I,Start), constraint(col,X,I,Len), row(X).
  rowcolor(Start..Start+Len-1,Y) :- rowrun(Y,I,Start), constraint(row,Y,I,Len), col(Y).
  
  % The inferred color from the row runs must be the same as those from the column runs.
  :- color(X,Y), not rowcolor(X,Y), row(X), col(Y).
  :- not color(X,Y), rowcolor(X,Y), row(X), col(Y).
  
  #hide.
  #show color/2.
  #show xmax/1.
  #show ymax/1.
  #show constraint/4.
  

• 10x10.lp (lists the constraints in the above 10x10 puzzle)
  

  #const ymax=10. #const xmax=10. #const maxruns=4.
  % constraints(col/row,I,A,B,C,...) - The lengths of blocks of filled-in
  % cells in column/row I are A,B,C,...
  
  constraints(col,1,1,2,3).
  constraints(col,2,1,2).
  constraints(col,3,2,5).
  constraints(col,4,4).
  constraints(col,5,6).
  constraints(col,6,6).
  constraints(col,7,1,3).
  constraints(col,8,8).
  constraints(col,9,1).
  constraints(col,10,2,3).
  constraints(row,1,3).
  constraints(row,2,1).
  constraints(row,3,3).
  constraints(row,4,1,1).
  constraints(row,5,1,1,2,1).
  constraints(row,6,1,6,1).
  constraints(row,7,4,1,1).
  constraints(row,8,1,6,1).
  constraints(row,9,8).
  constraints(row,10,2,4).
  

• display (Perl program to display the solution in human-readable form and check its validity against the original constraints)
  

  #!/usr/bin/perl
  
  use strict;
  use warnings;
  while (<>) {
    if (/color/) {
      my $xmax = 0;
      my $ymax = 0;
      my @color;
      my %constraint;
      while(/constraint[(](row|col),(\d+),(\d+),(\d+)/g) {
        $constraint{$1}[$2][$3-1] = $4;
      }
  
      while(/color[(](\d+),(\d+)/g) {
        $color[$1][$2] = 'b';
      }
      while(/ymax[(](\d+)/g) {
        $ymax = $1;
      }
      while(/xmax[(](\d+)/g) {
        $xmax = $1;
      }
      my $check = checksol(\@color, \%constraint, $xmax, $ymax);
      print if $check ne "OK"; # when debugging, show the raw data
      foreach my $y (1..$ymax) {
        foreach my $x (1..$xmax) {
          print $color[$x][$y] && $color[$x][$y] eq 'b' ? 'X' : '.', " ";
          print "  " if $x % 5 == 0 && $x > 0 && $x < $xmax;
        }
        print "\n";
        print "\n" if $y % 5 == 0 && $y > 0 && $y < $ymax;
      }
      print "$check\n";
    }
    else {
      print;
    }
  }
  
  
  
  sub checksol {
    my ($color, $constraint, $xmax, $ymax) = @_;
  
    foreach my $y (1..$ymax) {
      next unless $constraint->{'row'}[$y];
      my $row;
      foreach my $x (1..$xmax) {
        $row .= $color->[$x][$y] || " ";
      }
      my @counts = map length, $row =~ /(b+)/g;
      return "ERROR: row $y: @counts should be @{ $constraint->{'row'}[$y] }"
        if "@counts" ne "@{ $constraint->{'row'}[$y] }";
    }
    foreach my $x (1..$xmax) {
      next unless $constraint->{'col'}[$x];
      my $col;
      foreach my $y (1..$ymax) {
        $col .= $color->[$x][$y] || " ";
      }
      my @counts = map length, $col =~ /(b+)/g;
      return "ERROR: column $x: @counts should be @{ $constraint->{'col'}[$x] }"
        if "@counts" ne "@{ $constraint->{'col'}[$x] }";
    }
    return "OK";
  }
  

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).