this repo has no description
dekker.one
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%
23int: nrows;
24int: ncols;
25
26set of int: row = 1..nrows;
27set of int: col = 1..ncols;
28set of int: row_plus_one = 1..(nrows + 1);
29set of int: col_plus_one = 1..(ncols + 1);
30
31% The grid.
32%
33array [row, col] of var bool: a;
34
35% A generic row constraint.
36%
37predicate 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%
65predicate 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
91solve satisfy;
92
93output [ if fix(a[r, c]) then "# " else ". " endif ++
94 if c = ncols then "\n" else "" endif
95 | r in row, c in col
96 ];