Download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
/*
 
  Nonogram (Painting by numbers)  in Comet
   
  """
  Nonograms or Paint by Numbers 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.
  
  """
 
  See problem 12 at http://www.csplib.org/.
   
  
 
  This model uses the built-in constraint regular and Automaton.
  Compare this to my own home-brewn regular constraint in
 
 
  Many thanks to Pascal Van Hentenryck for the improvements which reduced the
  running time for the P200 problem from 1:30 minutes to about 1 second. The
  improvements are commented below. The significant best improvement was the
  (re)ordering of 1..rows / 1..cols in the labeling.
  
  The developments of this model has been written in the following blog posts
  (sorted in reversed order of publication):
 
  * "Comet: Nonogram improved: solving problem P200 from 1:30 minutes to about
    1 second"
 
  * "Comet: regular constraint, a much faster Nonogram with the regular
    constraint, some OPL models, and more"
 
  * "More Comet models, e.g. Nonogram, Steiner triplets, and different set covering
    problems"
 
 
  Also, compare with the following models:
    (older model, no regular constraint)
  * Gecode/R: http://www.hakank.org/gecode_r/nonogram.rb (using "regexps")
 
 
  This Comet model was created by Hakan Kjellerstrand (hakank@bonetmail.com)
  Also, see my Comet page: http://www.hakank.org/comet
 
 */
 
// Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
 
import cotfd;
int t0 = System.getCPUTime();
 
//
// Problems:
//
 
// The lambda picture
/*
int rows = 12;
int row_rule_len = 3;
int row_rules[1..rows, 1..row_rule_len] =
  [
   [0,0,2],
   [0,1,2],
   [0,1,1],
   [0,0,2],
   [0,0,1],
   [0,0,3],
   [0,0,3],
   [0,2,2],
   [0,2,1],
   [2,2,1],
   [0,2,3],
   [0,2,2]
   ];
 
int cols = 10;
int col_rule_len = 2;
int col_rules[1..cols, 1..col_rule_len] =
  [
   [2,1],
   [1,3],
   [2,4],
   [3,4],
   [0,4],
   [0,3],
   [0,3],
   [0,3],
   [0,2],
   [0,2]
   ];
*/
 
// Nonogram problem from Gecode: Dragonfly
// include "nonogram_dragonfly";
 
 
// Nonogram problem from Gecode: P200
// Statistics:
// Before improvements suggested by Pascal Van Hentenryck:
//  num_solutions: 1
//  time:      92726
//  #choices = 142167
//  #fail    = 284334
//  #propag  = 242312778
//  comet -j2 nonogram_regular.co  93,63s user 0,17s system 99% cpu 1:33,89 total
//
// With the improvements suggested by Pascal Van Hentenryck
// and my own implementation of regular (http://www.hakank.org/comet/nonogram_regular.co )
//   num_solutions: 1
//   time:      607
//   #choices = 520
//   #fail    = 1040
//   #propag  = 1213237
//   comet -j2 nonogram_regular.co  1,66s user 0,11s system 99% cpu 1,766 total
//
// With this model using Automaton and the built-in regular constraint.
//   num_solutions: 1
//   time:      437
//   #choices = 520
//   #fail    = 794
//   #propag  = 693993
//   comet -q nonogram_automaton.co  1,82s user 0,10s system 99% cpu 1,936 total
 
 
// data files should be imported from the "data" parent directory, for example
// include "../data/nonogram_p200";
 
// Nonogram problem from Wikipedia, soccer player
// include "nonogram_soccer_player";
 
 
Solver<CP> m();
 
//
// The grid
//
var<CP>{int} board[1..rows, 1..cols](m, 0..1);
 
 
Integer num_solutions(0);
// explore<m> {
exploreall<m> {
 
  forall(i in 1..rows) {
    check_rule(m, all(j in 1..row_rule_len) row_rules[i,j], all(j in 1..cols) board[i,j]);
  }
 
  forall(j in 1..cols) {
    check_rule(m, all(k in 1..col_rule_len) col_rules[j,k] , all(i in 1..rows) board[i, j]);
  }
 
} using {
 
  // Slightly different labelings depending on the size of the problem.
  // We start with the smaller dimension.
  // See above for credit to Pascal Van Hentenryck.
  if (rows * row_rule_len < cols * col_rule_len ) {
 
    forall(i in 1..rows, j in 1..cols: !board[i,j].bound()) {
      tryall<m>(v in 0..1) by (-v)
        m.label(board[i,j], v);
      onFailure m.diff(board[i,j], v);
    }
  } else {
 
    forall(j in 1..cols, i in 1..rows: !board[i,j].bound()) {
      tryall<m>(v in 0..1) by (-v)
        m.label(board[i,j], v);
      onFailure m.diff(board[i,j], v);
    }
  }
 
  num_solutions++;
  cout << "#fails  = " << m.getNFail() << endl;
  cout << "#propag  = " << m.getNPropag() << endl;
       
  forall(i in 1..rows) {
    forall(j in 1..cols) {
      string s = " ";
      if (board[i,j] == 1) {
        s = "#";
      }
      cout << s << "";
    }
    cout << endl;
  }
  cout << endl;
  cout << flush;
 
}
 
 
cout << "\nnum_solutions: " << num_solutions << endl;
     
int t1 = System.getCPUTime();
cout << "time:      " << (t1-t0) << endl;
cout << "#choices = " << m.getNChoice() << endl;
cout << "#fail    = " << m.getNFail() << endl;
cout << "#propag  = " << m.getNPropag() << endl;
 
//
// check_rule: The main function.
//
function void check_rule(Solver<CP> m, int[] rules, var<CP>{int}[] y) {
 
  int r_len = sum(i in 1..rules.getSize()) (rules[i] > 0);
  int rules_tmp[1..r_len];
  int c = 1;
  forall(i in 1..rules.getSize()) {
    if (rules[i] > 0) {
      rules_tmp[c] = rules[i];
      c++;
    }
  }
 
  Automaton<CP> aut =  make_automaton(rules_tmp);
  m.post(regular(y, aut));
 
} // end check_rule
 
 
//
// Build the transition matrix for a nonogram pattern.
//
function Automaton<CP> make_automaton(int[] pattern) {
 
  int p_len = pattern.getSize();
  int num_states = p_len + sum(i in 1..p_len) pattern[i];
 
  Automaton<CP> aut(1..num_states+1, 0..1, 1, {num_states, num_states+1});
 
  // convert pattern to a 0/1 pattern for easy handling of
  // the states
  int tmp[1..num_states];
  int c = 1;
  tmp[c] = 0;
  forall(i in 1..p_len) {
    forall(j in 1..pattern[i]) {
      tmp[++c] = 1;     
    }
    if (c < num_states) {
        tmp[++c] = 0;
    }
  }
 
  // create the transition states
  forall(i in 1..num_states) {
    if (tmp[i] == 0) {
      aut.addTransition(i,i,0);
      aut.addTransition(i,i+1,1);
    } else {
      if (i < num_states) {
        if (tmp[i+1] == 1) {
          aut.addTransition(i,i+1,1);
        } else {
          aut.addTransition(i,i+1,0);
        }
      }
    }
  }
 
  aut.addTransition(num_states,num_states+1,0);
  aut.addTransition(num_states+1,num_states+1,0);
 
  return aut; 
 
} // end make_automaton