alpar@1: /* PBN, Paint-By-Numbers Puzzle */
alpar@1: 
alpar@1: /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@1: 
alpar@1: /* A paint-by-number puzzle consists of an m*n grid of pixels (the
alpar@1:    canvas) together with m+n cluster-size sequences, one for each row
alpar@1:    and column. The goal is to paint the canvas with a picture that
alpar@1:    satisfies the following constraints:
alpar@1: 
alpar@1:    1. Each pixel must be blank or white.
alpar@1: 
alpar@1:    2. If a row or column has cluster-size sequence s1, s2, ..., sk,
alpar@1:       then it must contain k clusters of black pixels - the first with
alpar@1:       s1 black pixels, the second with s2 black pixels, and so on.
alpar@1: 
alpar@1:    It should be noted that "first" means "leftmost" for rows and
alpar@1:    "topmost" for columns, and that rows and columns need not begin or
alpar@1:    end with black pixels.
alpar@1: 
alpar@1:    Example:
alpar@1:                   1   1
alpar@1:                   1   1
alpar@1:               2 1 1 1 1 1 2 3
alpar@1:               3 2 1 2 1 2 3 4 8 9
alpar@1: 
alpar@1:         3 6   # # # . # # # # # #
alpar@1:         1 4   # . . . . . # # # #
alpar@1:       1 1 3   . . # . # . . # # #
alpar@1:           2   . . . . . . . . # #
alpar@1:         3 3   . . # # # . . # # #
alpar@1:         1 4   # . . . . . # # # #
alpar@1:         2 5   # # . . . # # # # #
alpar@1:         2 5   # # . . . # # # # #
alpar@1:         1 1   . . . # . . . . . #
alpar@1:           3   . . # # # . . . . .
alpar@1: 
alpar@1:    (In Russia this sort of puzzles is known as "Japanese crossword".)
alpar@1: 
alpar@1:    References:
alpar@1:    Robert A. Bosch, "Painting by Numbers", 2000.
alpar@1:    <http://www.oberlin.edu/~math/faculty/bosch/pbn-page.html> */
alpar@1: 
alpar@1: param m, integer, >= 1;
alpar@1: /* the number of rows */
alpar@1: 
alpar@1: param n, integer, >= 1;
alpar@1: /* the number of columns */
alpar@1: 
alpar@1: param row{i in 1..m, 1..n div 2}, integer, >= 0, default 0;
alpar@1: /* the cluster-size sequence for row i (raw data) */
alpar@1: 
alpar@1: param col{j in 1..n, 1..m div 2}, integer, >= 0, default 0;
alpar@1: /* the cluster-size sequence for column j (raw data) */
alpar@1: 
alpar@1: param kr{i in 1..m} := sum{t in 1..n div 2: row[i,t] > 0} 1;
alpar@1: /* the number of clusters in row i */
alpar@1: 
alpar@1: param kc{j in 1..n} := sum{t in 1..m div 2: col[j,t] > 0} 1;
alpar@1: /* the number of clusters in column j */
alpar@1: 
alpar@1: param sr{i in 1..m, t in 1..kr[i]} := row[i,t], integer, >= 1;
alpar@1: /* the cluster-size sequence for row i */
alpar@1: 
alpar@1: param sc{j in 1..n, t in 1..kc[j]} := col[j,t], integer, >= 1;
alpar@1: /* the cluster-size sequence for column j */
alpar@1: 
alpar@1: check{i in 1..m}: sum{t in 1..kr[i]} sr[i,t] <= n - (kr[i] - 1);
alpar@1: /* check that the sum of the cluster sizes in each row is valid */
alpar@1: 
alpar@1: check{j in 1..n}: sum{t in 1..kc[j]} sc[j,t] <= m - (kc[j] - 1);
alpar@1: /* check that the sum of the cluster sizes in each column is valid */
alpar@1: 
alpar@1: check: sum{i in 1..m, t in 1..kr[i]} sr[i,t] =
alpar@1:        sum{j in 1..n, t in 1..kc[j]} sc[j,t];
alpar@1: /* check that the sum of the cluster sizes in all rows is equal to the
alpar@1:    sum of the cluster sizes in all columns */
alpar@1: 
alpar@1: param er{i in 1..m, t in 1..kr[i]} :=
alpar@1:    if t = 1 then 1 else er[i,t-1] + sr[i,t-1] + 1;
alpar@1: /* the smallest value of j such that row i's t-th cluster can be
alpar@1:    placed in row i with its leftmost pixel occupying pixel j */
alpar@1: 
alpar@1: param lr{i in 1..m, t in 1..kr[i]} :=
alpar@1:    if t = kr[i] then n + 1 - sr[i,t] else lr[i,t+1] - sr[i,t] - 1;
alpar@1: /* the largest value of j such that row i's t-th cluster can be
alpar@1:    placed in row i with its leftmost pixel occupying pixel j */
alpar@1: 
alpar@1: param ec{j in 1..n, t in 1..kc[j]} :=
alpar@1:    if t = 1 then 1 else ec[j,t-1] + sc[j,t-1] + 1;
alpar@1: /* the smallest value of i such that column j's t-th cluster can be
alpar@1:    placed in column j with its topmost pixel occupying pixel i */
alpar@1: 
alpar@1: param lc{j in 1..n, t in 1..kc[j]} :=
alpar@1:    if t = kc[j] then m + 1 - sc[j,t] else lc[j,t+1] - sc[j,t] - 1;
alpar@1: /* the largest value of i such that column j's t-th cluster can be
alpar@1:    placed in column j with its topmost pixel occupying pixel i */
alpar@1: 
alpar@1: var z{i in 1..m, j in 1..n}, binary;
alpar@1: /* z[i,j] = 1, if row i's j-th pixel is painted black
alpar@1:    z[i,j] = 0, if row i's j-th pixel is painted white */
alpar@1: 
alpar@1: var y{i in 1..m, t in 1..kr[i], j in er[i,t]..lr[i,t]}, binary;
alpar@1: /* y[i,t,j] = 1, if row i's t-th cluster is placed in row i with its
alpar@1:                  leftmost pixel occupying pixel j
alpar@1:    y[i,t,j] = 0, if not */
alpar@1: 
alpar@1: var x{j in 1..n, t in 1..kc[j], i in ec[j,t]..lc[j,t]}, binary;
alpar@1: /* x[j,t,i] = 1, if column j's t-th cluster is placed in column j with
alpar@1:                  its topmost pixel occupying pixel i
alpar@1:    x[j,t,i] = 0, if not */
alpar@1: 
alpar@1: s.t. fa{i in 1..m, t in 1..kr[i]}:
alpar@1:      sum{j in er[i,t]..lr[i,t]} y[i,t,j] = 1;
alpar@1: /* row i's t-th cluster must appear in row i exactly once */
alpar@1: 
alpar@1: s.t. fb{i in 1..m, t in 1..kr[i]-1, j in er[i,t]..lr[i,t]}:
alpar@1:      y[i,t,j] <= sum{jp in j+sr[i,t]+1..lr[i,t+1]} y[i,t+1,jp];
alpar@1: /* row i's (t+1)-th cluster must be placed to the right of its t-th
alpar@1:    cluster */
alpar@1: 
alpar@1: s.t. fc{j in 1..n, t in 1..kc[j]}:
alpar@1:      sum{i in ec[j,t]..lc[j,t]} x[j,t,i] = 1;
alpar@1: /* column j's t-th cluster must appear in column j exactly once */
alpar@1: 
alpar@1: s.t. fd{j in 1..n, t in 1..kc[j]-1, i in ec[j,t]..lc[j,t]}:
alpar@1:      x[j,t,i] <= sum{ip in i+sc[j,t]+1..lc[j,t+1]} x[j,t+1,ip];
alpar@1: /* column j's (t+1)-th cluster must be placed below its t-th cluster */
alpar@1: 
alpar@1: s.t. fe{i in 1..m, j in 1..n}:
alpar@1:      z[i,j] <= sum{t in 1..kr[i], jp in er[i,t]..lr[i,t]:
alpar@1:                    j-sr[i,t]+1 <= jp and jp <= j} y[i,t,jp];
alpar@1: /* the double coverage constraint stating that if row i's j-th pixel
alpar@1:    is painted black, then at least one of row i's clusters must be
alpar@1:    placed in such a way that it covers row i's j-th pixel */
alpar@1: 
alpar@1: s.t. ff{i in 1..m, j in 1..n}:
alpar@1:      z[i,j] <= sum{t in 1..kc[j], ip in ec[j,t]..lc[j,t]:
alpar@1:                    i-sc[j,t]+1 <= ip and ip <= i} x[j,t,ip];
alpar@1: /* the double coverage constraint making sure that if row i's j-th
alpar@1:    pixel is painted black, then at least one of column j's clusters
alpar@1:    covers it */
alpar@1: 
alpar@1: s.t. fg{i in 1..m, j in 1..n, t in 1..kr[i], jp in er[i,t]..lr[i,t]:
alpar@1:      j-sr[i,t]+1 <= jp and jp <= j}: z[i,j] >= y[i,t,jp];
alpar@1: /* the constraint to prevent white pixels from being covered by the
alpar@1:    row clusters */
alpar@1: 
alpar@1: s.t. fh{i in 1..m, j in 1..n, t in 1..kc[j], ip in ec[j,t]..lc[j,t]:
alpar@1:      i-sc[j,t]+1 <= ip and ip <= i}: z[i,j] >= x[j,t,ip];
alpar@1: /* the constraint to prevent white pixels from being covered by the
alpar@1:    column clusters */
alpar@1: 
alpar@1: /* there is no need for an objective function here */
alpar@1: 
alpar@1: solve;
alpar@1: 
alpar@1: for {i in 1..m}
alpar@1: {  printf{j in 1..n} " %s", if z[i,j] then "#" else ".";
alpar@1:    printf "\n";
alpar@1: }
alpar@1: 
alpar@1: data;
alpar@1: 
alpar@1: /* These data correspond to the example above. */
alpar@1: 
alpar@1: param m := 10;
alpar@1: 
alpar@1: param n := 10;
alpar@1: 
alpar@1: param row : 1 2 3 4 :=
alpar@1:          1  3 6 . .
alpar@1:          2  1 4 . .
alpar@1:          3  1 1 3 .
alpar@1:          4  2 . . .
alpar@1:          5  3 3 . .
alpar@1:          6  1 4 . .
alpar@1:          7  2 5 . .
alpar@1:          8  2 5 . .
alpar@1:          9  1 1 . .
alpar@1:         10  3 . . . ;
alpar@1: 
alpar@1: param col : 1 2 3 4 :=
alpar@1:          1  2 3 . .
alpar@1:          2  1 2 . .
alpar@1:          3  1 1 1 1
alpar@1:          4  1 2 . .
alpar@1:          5  1 1 1 1
alpar@1:          6  1 2 . .
alpar@1:          7  2 3 . .
alpar@1:          8  3 4 . .
alpar@1:          9  8 . . .
alpar@1:         10  9 . . . ;
alpar@1: 
alpar@1: end;