| 1 |
% tenpenki.mzn |
| 2 |
% vim: ft=zinc ts=4 sw=4 et |
| 3 |
% Ralph Becket |
| 4 |
% Thu Aug 14 15:23:11 EST 2008 |
| 5 |
% |
| 6 |
% A tenpenki puzzle involves filling out the pixels in a grid to make |
| 7 |
% a picture. Each row/column constraint specifies the distinct |
| 8 |
% runs of "black" pixels in that row/column. For example, |
| 9 |
% |
| 10 |
% 1 1 |
| 11 |
% 1 2 1 1 |
| 12 |
% 1 1 5 2 1 |
| 13 |
% +-----------+ |
| 14 |
% 1 3 | # . # # # | |
| 15 |
% 2 | . # # . . | |
| 16 |
% 5 | # # # # # | |
| 17 |
% 2 | . . # # . | |
| 18 |
% 3 1 | # # # . # | |
| 19 |
% +-----------+ |
| 20 |
|
| 21 |
% The dimensions of the board. |
| 22 |
% |
| 23 |
int: nrows; |
| 24 |
int: ncols; |
| 25 |
|
| 26 |
set of int: row = 1..nrows; |
| 27 |
set of int: col = 1..ncols; |
| 28 |
set of int: row_plus_one = 1..(nrows + 1); |
| 29 |
set of int: col_plus_one = 1..(ncols + 1); |
| 30 |
|
| 31 |
% The grid. |
| 32 |
% |
| 33 |
array [row, col] of var bool: a; |
| 34 |
|
| 35 |
% A generic row constraint. |
| 36 |
% |
| 37 |
predicate row_constraint(row: r, array [int] of col: x) = |
| 38 |
if index_set(x) = {} then |
| 39 |
forall (c in col) (a[r, c] = false) |
| 40 |
else |
| 41 |
let { |
| 42 |
int: n = max(index_set(x)), |
| 43 |
array [1..n] of var col: s % The starting col of each block. |
| 44 |
} in ( |
| 45 |
% There must be at least one white cell between each black block. |
| 46 |
% |
| 47 |
forall (i in 1..(n - 1)) (s[i + 1] > s[i] + x[i]) |
| 48 |
/\ |
| 49 |
% The final black block mustn't overrun the row. |
| 50 |
% |
| 51 |
s[n] + x[n] <= ncols + 1 |
| 52 |
/\ |
| 53 |
% Ensure that the pixels in this row are coloured in appropriately. |
| 54 |
% |
| 55 |
forall (c in col) ( |
| 56 |
a[r, c] |
| 57 |
<-> |
| 58 |
exists (i in 1..n) (s[i] <= c /\ c < s[i] + x[i]) |
| 59 |
) |
| 60 |
) |
| 61 |
endif; |
| 62 |
|
| 63 |
% A generic col constraint. |
| 64 |
% |
| 65 |
predicate col_constraint(col: c, array [int] of row: x) = |
| 66 |
if index_set(x) = {} then |
| 67 |
forall (r in row) (a[r, c] = false) |
| 68 |
else |
| 69 |
let { |
| 70 |
int: n = max(index_set(x)), |
| 71 |
array [1..n] of var row: s % The starting row of each block. |
| 72 |
} in ( |
| 73 |
% There must be at least one white cell between each black block. |
| 74 |
% |
| 75 |
forall (i in 1..(n - 1)) (s[i + 1] > s[i] + x[i]) |
| 76 |
/\ |
| 77 |
% The final black block mustn't overrun the col. |
| 78 |
% |
| 79 |
s[n] + x[n] <= ncols + 1 |
| 80 |
/\ |
| 81 |
% Ensure that the pixels in this col are coloured in appropriately. |
| 82 |
% |
| 83 |
forall (r in row) ( |
| 84 |
a[r, c] |
| 85 |
<-> |
| 86 |
exists (i in 1..n) (s[i] <= r /\ r < s[i] + x[i]) |
| 87 |
) |
| 88 |
) |
| 89 |
endif; |
| 90 |
|
| 91 |
solve satisfy; |
| 92 |
|
| 93 |
output [ if fix(a[r, c]) then "# " else ". " endif ++ |
| 94 |
if c = ncols then "\n" else "" endif |
| 95 |
| r in row, c in col |
| 96 |
]; |