Generated on Mon Jul 27 2020 00:00:00 for Gecode by doxygen 1.8.18
nonogram.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Mikael Lagerkvist <lagerkvist@gecode.org>
5  *
6  * Copyright:
7  * Mikael Lagerkvist, 2005
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/driver.hh>
35 #include <gecode/int.hh>
36 #include <gecode/minimodel.hh>
37 
38 
39 using namespace Gecode;
40 
41 namespace {
42 
44  extern const int* specs[];
46  extern const unsigned int n_examples;
47 
48 }
49 
67 class Nonogram : public Script {
68 protected:
70  const int* spec;
73 
75  int width(void) const {
76  return spec[0];
77  }
79  int height(void) const {
80  return spec[1];
81  }
82 
84  DFA line(int& spos) {
85  REG r0(0), r1(1);
86  REG border = *r0;
87  REG between = +r0;
88  int hints = spec[spos++];
89  REG r = border;
90  if (hints > 0) {
91  r += r1(spec[spos],spec[spos]);
92  spos++;
93  for (int i=hints-1; i--; spos++)
94  r += between + r1(spec[spos],spec[spos]);
95  }
96  return r + border;
97  }
98 
99 public:
100  // Branching variants
101  enum {
104  };
105 
108  : Script(opt), spec(specs[opt.size()]), b(*this,width()*height(),0,1) {
109  Matrix<BoolVarArray> m(b, width(), height());
110 
111  {
112  int spos = 2;
113  // Post constraints for columns
114  for (int w=0; w<width(); w++)
115  extensional(*this, m.col(w), line(spos));
116  // Post constraints for rows
117  for (int h=0; h<height(); h++)
118  extensional(*this, m.row(h), line(spos));
119  }
120 
121 
122 
123  switch (opt.branching()) {
124  case BRANCH_NONE:
125  {
126  /*
127  * The following branches either by columns or rows, depending on
128  * whether there are more hints relative to the height or width
129  * for columns or rows.
130  *
131  * This idea is due to Pascal Van Hentenryck and has been suggested
132  * to us by Hakan Kjellerstrand.
133  */
134 
135  // Number of hints for columns
136  int cols = 0;
137  // Number of hints for rows
138  int rows = 0;
139  int spos = 2;
140  for (int w=0; w<width(); w++) {
141  int hint = spec[spos++];
142  cols += hint; spos += hint;
143  }
144  for (int h=0; h<height(); h++) {
145  int hint = spec[spos++];
146  rows += hint; spos += hint;
147  }
148 
149  if (rows*width() > cols*height()) {
150  for (int w=0; w<width(); w++)
151  branch(*this, m.col(w), BOOL_VAR_NONE(), BOOL_VAL_MAX());
152  } else {
153  for (int h=0; h<height(); h++)
154  branch(*this, m.row(h), BOOL_VAR_NONE(), BOOL_VAL_MAX());
155  }
156  }
157  break;
158  case BRANCH_AFC:
159  /*
160  * The following just uses the AFC for branching. This is
161  * equivalent to SIZE/AFC in this case since the variables are
162  * binary.
163  */
164  branch(*this, b, BOOL_VAR_AFC_MAX(opt.decay()), BOOL_VAL_MAX());
165  break;
166  }
167  }
168 
170  Nonogram(Nonogram& s) : Script(s), spec(s.spec) {
171  b.update(*this, s.b);
172  }
173 
175  virtual Space*
176  copy(void) {
177  return new Nonogram(*this);
178  }
179 
181  virtual void
182  print(std::ostream& os) const {
183  Matrix<BoolVarArray> m(b, width(), height());
184  for (int h = 0; h < height(); ++h) {
185  os << '\t';
186  for (int w = 0; w < width(); ++w)
187  os << ((m(w,h).val() == 1) ? '#' : ' ');
188  os << std::endl;
189  }
190  os << std::endl;
191  }
192 };
193 
194 
198 int
199 main(int argc, char* argv[]) {
200  SizeOptions opt("Nonogram");
201  opt.size(8);
204  "Branch on rows/columns in order");
206  "Use AFC for branching");
207  opt.parse(argc,argv);
208  if (opt.size() >= n_examples) {
209  std::cerr << "Error: size must be between 0 and "
210  << n_examples-1 << std::endl;
211  return 1;
212  }
213  Script::run<Nonogram,DFS,SizeOptions>(opt);
214  return 0;
215 }
216 
217 namespace {
218 
230 const int heart[] =
232  { 9, 9,
233  // Column constraints.
234  1, 3,
235  2, 2, 3,
236  2, 2, 2,
237  2, 2, 2,
238  2, 2, 2,
239  2, 2, 2,
240  2, 2, 2,
241  2, 2, 3,
242  1, 3,
243  // Row constraints
244  2, 2, 2,
245  2, 4, 4,
246  3, 1, 3, 1,
247  3, 2, 1, 2,
248  2, 1, 1,
249  2, 2, 2,
250  2, 2, 2,
251  1, 3,
252  1, 1
253  };
254 
256 const int bear[] =
257  { 13, 8,
258  // Column constraints
259  1, 2,
260  2, 2, 1,
261  2, 3, 2,
262  1, 6,
263  2, 1, 4,
264  1, 3,
265  1, 4,
266  1, 4,
267  1, 4,
268  1, 5,
269  1, 4,
270  2, 1, 3,
271  1, 2,
272  // Row constraints
273  1, 1,
274  1, 2,
275  2, 4, 4,
276  1, 12,
277  1, 8,
278  1, 9,
279  2, 3, 4,
280  2, 2, 2
281  };
282 
284 const int crocodile[] =
285  { 15, 9,
286  // Column constraints
287  1, 3,
288  1, 4,
289  2, 2, 2,
290  2, 3, 1,
291  2, 2, 3,
292  2, 3, 2,
293  2, 2, 3,
294  2, 4, 2,
295  2, 3, 2,
296  1, 6,
297  2, 1, 3,
298  2, 1, 3,
299  2, 1, 4,
300  1, 5,
301  1, 5,
302  // Row constraints
303  1, 3,
304  3, 2, 3, 2,
305  2, 10, 3,
306  1, 15,
307  5, 1, 1, 1, 1, 6,
308  2, 1, 7,
309  2, 1, 4,
310  2, 1, 4,
311  1, 4
312  };
313 
315 const int unknown[] =
316  { 10, 10,
317  // Column constraints
318  1, 3,
319  2, 2, 1,
320  2, 2, 2,
321  2, 2, 1,
322  3, 1, 2, 1,
323  2, 1, 1,
324  3, 1, 4, 1,
325  3, 1, 1, 2,
326  2, 3, 1,
327  1, 4,
328  // Row constraints
329  1, 3,
330  2, 2, 1,
331  2, 1, 1,
332  2, 1, 4,
333  4, 1, 1, 1, 1,
334  4, 2, 1, 1, 1,
335  3, 2, 1, 1,
336  2, 1, 2,
337  2, 2, 3,
338  1, 3
339  };
340 
342 const int pinwheel[] =
343  { 6, 6,
344  // Column constraints
345  2, 1, 2,
346  1, 1,
347  1, 2,
348  1, 2,
349  1, 1,
350  2, 2, 1,
351  // Row constraints
352  2, 2, 1,
353  1, 1,
354  1, 2,
355  1, 2,
356  1, 1,
357  2, 1, 2
358  };
359 
361 const int difficult[] =
362  { 15, 15,
363  // Column constraints
364  1, 3,
365  1, 2,
366  1, 2,
367  1, 1,
368  1, 2,
369  1, 3,
370  1, 2,
371  1, 4,
372  1, 3,
373  1, 4,
374  2, 2, 1,
375  2, 1, 1,
376  2, 1, 1,
377  2, 1, 1,
378  1, 3,
379  // Row constraints
380  1, 3,
381  2, 1, 1,
382  2, 1, 1,
383  2, 1, 1,
384  2, 1, 2,
385  1, 5,
386  1, 1,
387  1, 2,
388  1, 1,
389  1, 1,
390  2, 1, 2,
391  2, 1, 2,
392  2, 2, 1,
393  2, 2, 2,
394  1, 3
395  };
396 
398 const int non_unique[] =
399  { 11, 15,
400  // Column constraints
401  1, 5,
402  3, 1, 2, 4,
403  3, 2, 1, 3,
404  4, 2, 2, 1, 1,
405  4, 1, 1, 1, 1,
406  2, 1, 5,
407  5, 2, 1, 1, 3, 2,
408  5, 2, 1, 1, 1, 1,
409  3, 1, 4, 1,
410  2, 1, 1,
411  1, 1,
412  // Row constraints
413  2, 2, 2,
414  2, 2, 2,
415  1, 4,
416  2, 1, 1,
417  2, 1, 1,
418  4, 1, 1, 1, 1,
419  2, 1, 1,
420  2, 1, 4,
421  3, 1, 1, 1,
422  3, 1, 1, 4,
423  2, 1, 3,
424  2, 1, 2,
425  1, 5,
426  2, 2, 2,
427  2, 3, 3
428  };
429 
435  const int dragonfly[] =
436  { 20, 20,
437  // Column constraints.
438  4, 1, 1, 1, 2,
439  5, 3, 1, 2, 1, 1,
440  5, 1, 4, 2, 1, 1,
441  4, 1, 3, 2, 4,
442  4, 1, 4, 6, 1,
443  3, 1, 11, 1,
444  4, 5, 1, 6, 2,
445  1, 14,
446  2, 7, 2,
447  2, 7, 2,
448  3, 6, 1, 1,
449  2, 9, 2,
450  4, 3, 1, 1, 1,
451  3, 3, 1, 3,
452  3, 2, 1, 3,
453  3, 2, 1, 5,
454  3, 3, 2, 2,
455  3, 3, 3, 2,
456  3, 2, 3, 2,
457  2, 2, 6,
458  // Row constraints
459  2, 7, 1,
460  3, 1, 1, 2,
461  3, 2, 1, 2,
462  3, 1, 2, 2,
463  3, 4, 2, 3,
464  3, 3, 1, 4,
465  3, 3, 1, 3,
466  3, 2, 1, 4,
467  2, 2, 9,
468  3, 2, 1, 5,
469  2, 2, 7,
470  1, 14,
471  2, 8, 2,
472  3, 6, 2, 2,
473  4, 2, 8, 1, 3,
474  4, 1, 5, 5, 2,
475  5, 1, 3, 2, 4, 1,
476  5, 3, 1, 2, 4, 1,
477  5, 1, 1, 3, 1, 3,
478  4, 2, 1, 1, 2
479  };
480 
482  const int castle[] = {
483  60, 35,
484  // Column constraints
485  7, 2,3,1,5,1,7,1,
486  7, 2,4,2,3,2,3,5,
487  8, 2,6,3,1,1,5,1,5,
488  10, 2,4,2,1,1,1,4,1,1,2,
489  7, 2,8,2,1,5,2,5,
490  7, 3,1,6,2,5,1,5,
491  9, 3,3,3,1,1,6,1,1,1,
492  9, 3,2,2,2,2,8,1,1,3,
493  7, 1,4,4,3,7,1,1,
494  7, 1,2,2,2,3,7,9,
495  8, 1,2,3,1,1,5,2,2,
496  7, 2,2,3,1,1,6,1,
497  6, 1,3,1,5,4,1,
498  8, 1,3,1,1,6,1,3,1,
499  8, 3,3,4,5,1,4,2,1,
500  6, 2,3,3,9,7,1,
501  8, 2,3,2,2,1,1,3,5,
502  8, 4,2,1,1,1,1,2,3,
503  7, 4,2,2,1,4,3,2,
504  4, 4,3,16,2,
505  5, 1,2,5,7,1,
506  6, 4,3,2,2,7,1,
507  5, 2,3,1,10,1,
508  6, 2,4,2,1,4,1,
509  5, 1,6,7,3,1,
510  4, 3,11,3,1,
511  5, 7,1,11,2,1,
512  7, 2,2,2,2,2,2,2,
513  7, 3,1,1,1,1,2,1,
514  7, 2,2,2,2,1,1,1,
515  7, 1,1,1,1,2,1,2,
516  8, 2,2,2,2,1,1,1,1,
517  5, 4,1,1,2,2,
518  5, 5,2,17,2,1,
519  6, 9,2,3,1,4,2,
520  6, 9,4,2,1,1,1,
521  5, 5,4,2,1,4,
522  7, 11,1,2,1,4,1,2,
523  5, 3,4,2,4,4,
524  8, 2,1,4,1,2,1,5,2,
525  5, 8,4,1,1,2,
526  5, 1,1,3,2,3,
527  6, 1,3,1,8,1,6,
528  4, 2,1,7,14,
529  7, 1,2,4,4,1,2,3,
530  10, 1,1,4,2,1,1,1,1,1,4,
531  6, 3,5,3,1,1,4,
532  6, 2,4,2,2,1,2,
533  5, 4,2,3,8,4,
534  5, 4,15,2,2,4,
535  6, 4,1,10,2,1,2,
536  6, 2,12,6,1,2,4,
537  7, 3,1,3,1,3,3,4,
538  6, 3,1,2,3,4,1,
539  7, 5,2,2,2,3,3,3,
540  9, 1,2,2,2,2,4,1,1,3,
541  7, 2,1,4,2,7,1,1,
542  6, 5,2,2,3,6,3,
543  7, 3,3,2,2,3,2,3,
544  7, 4,1,2,1,1,2,1,
545 
546  // Row constraints
547  4, 12,1,1,1,
548  5, 8,6,3,1,3,
549  6, 5,8,4,3,1,5,
550  8, 7,3,4,1,3,5,1,7,
551  13, 2,2,4,9,1,5,1,1,1,1,1,1,1,
552  8, 4,5,10,2,1,8,7,1,
553  7, 5,1,3,3,16,1,2,
554  8, 8,5,1,2,4,9,1,3,
555  12, 4,5,3,14,1,1,1,1,4,1,1,3,
556  19, 3,3,2,2,2,4,1,1,1,1,1,1,1,1,3,1,1,3,2,
557  11, 8,2,7,2,1,1,2,1,1,3,3,
558  13, 1,5,9,12,2,1,1,3,1,1,2,2,1,
559  17, 3,2,2,1,1,1,1,4,1,1,1,3,3,1,1,2,2,
560  12, 5,2,2,2,2,1,5,2,1,1,2,5,
561  12, 3,5,9,2,1,1,6,3,1,3,2,3,
562  12, 1,4,1,1,1,4,1,5,5,3,3,3,
563  10, 4,1,1,1,1,3,4,6,6,3,
564  12, 3,1,3,1,1,3,3,1,1,4,6,1,
565  11, 3,1,5,1,1,3,1,1,9,4,1,
566  14, 2,1,1,7,1,4,1,1,1,1,1,1,3,5,
567  11, 9,2,1,3,1,1,1,1,4,2,1,
568  10, 1,14,1,1,2,2,2,10,1,2,
569  10, 1,9,2,1,2,6,1,5,3,2,
570  12, 1,9,9,1,2,2,3,1,1,4,3,1,
571  10, 10,1,3,4,1,3,2,1,2,8,
572  9, 9,1,3,5,1,1,1,2,7,
573  12, 4,5,1,2,5,1,3,1,1,2,1,3,
574  14, 1,1,1,1,2,6,2,3,2,1,1,2,3,1,
575  11, 1,6,1,5,7,1,3,3,2,4,3,
576  10, 1,2,1,2,9,1,5,2,6,2,
577  8, 10,2,2,13,1,3,3,1,
578  11, 2,2,1,6,2,3,3,2,2,2,1,
579  12, 2,2,1,1,12,2,2,9,2,2,2,2,
580  9, 5,1,2,4,1,5,11,2,2,
581  3, 15,6,18,
582  };
583 
589  const int p200[] =
590  { 25, 25,
591  // Column constraints
592  4, 1,1,2,2,
593  3, 5,5,7,
594  4, 5,2,2,9,
595  4, 3,2,3,9,
596  5, 1,1,3,2,7,
597  3, 3,1,5,
598  5, 7,1,1,1,3,
599  6, 1,2,1,1,2,1,
600  3, 4,2,4,
601  4, 1,2,2,2,
602  3, 4,6,2,
603  4, 1,2,2,1,
604  4, 3,3,2,1,
605  3, 4,1,15,
606  6, 1,1,1,3,1,1,
607  6, 2,1,1,2,2,3,
608  4, 1,4,4,1,
609  4, 1,4,3,2,
610  4, 1,1,2,2,
611  5, 7,2,3,1,1,
612  5, 2,1,1,1,5,
613  3, 1,2,5,
614  4, 1,1,1,3,
615  3, 4,2,1,
616  1, 3,
617  // Row constraints
618  3, 2,2,3,
619  5, 4,1,1,1,4,
620  5, 4,1,2,1,1,
621  7, 4,1,1,1,1,1,1,
622  6, 2,1,1,2,3,5,
623  6, 1,1,1,1,2,1,
624  5, 3,1,5,1,2,
625  6, 3,2,2,1,2,2,
626  7, 2,1,4,1,1,1,1,
627  6, 2,2,1,2,1,2,
628  6, 1,1,1,3,2,3,
629  5, 1,1,2,7,3,
630  5, 1,2,2,1,5,
631  5, 3,2,2,1,2,
632  4, 3,2,1,2,
633  3, 5,1,2,
634  4, 2,2,1,2,
635  4, 4,2,1,2,
636  4, 6,2,3,2,
637  4, 7,4,3,2,
638  3, 7,4,4,
639  3, 7,1,4,
640  3, 6,1,4,
641  3, 4,2,2,
642  2, 2,1
643  };
644 
645  // The following instances are from the http://webpbn.com site and
646  // are all designed by Jan Wolter.
647  // See also the survey at http://webpbn.com/survey/
648 
650  const int webpbn436[]=
651  { 40, 35,
652  // Column constraints
653  1, 1,
654  2, 3, 2,
655  3, 2, 3, 3,
656  3, 3, 3, 3,
657  4, 3, 3, 3, 3,
658  4, 4, 2, 2, 2,
659  4, 3, 3, 2, 3,
660  4, 3, 2, 2, 2,
661  3, 3, 2, 6,
662  2, 2, 9,
663  3, 2, 3, 3,
664  5, 4, 4, 3, 2, 4,
665  5, 7, 2, 5, 2, 6,
666  6, 12, 2, 3, 2, 3, 2,
667  6, 3, 1, 2, 2, 2, 3,
668  6, 2, 2, 3, 2, 2, 2,
669  6, 6, 2, 6, 2, 2, 2,
670  5, 12, 4, 3, 2, 2,
671  4, 12, 2, 2, 2,
672  3, 2, 6, 2,
673  4, 2, 6, 5, 2,
674  4, 10, 9, 2, 2,
675  5, 12, 3, 3, 2, 2,
676  7, 6, 2, 2, 2, 2, 2, 2,
677  6, 2, 2, 3, 2, 2, 2,
678  6, 4, 3, 2, 2, 2, 3,
679  6, 7, 3, 3, 2, 3, 2,
680  5, 5, 3, 5, 2, 6,
681  5, 4, 3, 3, 3, 4,
682  3, 3, 5, 3,
683  2, 3, 9,
684  3, 4, 2, 6,
685  4, 4, 2, 2, 2,
686  4, 4, 2, 2, 3,
687  4, 3, 2, 2, 3,
688  3, 3, 3, 3,
689  3, 3, 3, 3,
690  3, 4, 3, 3,
691  3, 2, 3, 3,
692  2, 2, 1,
693  // Row constraints
694  2, 2, 2,
695  3, 2, 3, 2,
696  4, 3, 3, 3, 2,
697  4, 3, 3, 3, 3,
698  6, 2, 3, 3, 3, 3, 2,
699  6, 3, 3, 3, 3, 3, 3,
700  6, 4, 2, 3, 2, 2, 4,
701  7, 4, 2, 2, 2, 2, 3, 1,
702  7, 3, 1, 2, 2, 2, 3, 3,
703  7, 3, 2, 2, 2, 2, 2, 4,
704  5, 3, 2, 15, 2, 4,
705  3, 5, 19, 4,
706  4, 6, 4, 3, 3,
707  3, 6, 4, 4,
708  4, 2, 4, 6, 2,
709  6, 2, 2, 3, 3, 3, 2,
710  6, 9, 2, 2, 2, 3, 9,
711  7, 10, 2, 2, 2, 2, 2, 10,
712  9, 4, 2, 3, 3, 2, 2, 3, 2, 5,
713  5, 2, 5, 2, 4, 2,
714  5, 5, 3, 2, 2, 5,
715  5, 6, 3, 2, 3, 7,
716  4, 6, 8, 9, 7,
717  4, 4, 8, 7, 5,
718  1, 4,
719  1, 2,
720  1, 2,
721  1, 14,
722  1, 16,
723  2, 3, 3,
724  2, 2, 2,
725  2, 2, 2,
726  2, 4, 4,
727  1, 16,
728  1, 12,
729  };
730 
732  const int webpbn21[]=
733  { 14, 25,
734  // Column constraints
735  1, 2,
736  2, 4, 6,
737  4, 9, 4, 4, 2,
738  4, 1, 6, 2, 6,
739  3, 1, 5, 2,
740  2, 1, 6,
741  2, 1, 5,
742  2, 1, 4,
743  2, 1, 4,
744  3, 1, 4, 2,
745  3, 1, 4, 6,
746  5, 1, 6, 4, 4, 2,
747  3, 9, 2, 6,
748  2, 4, 2,
749  // Row constraints
750  1, 9,
751  2, 1, 1,
752  3, 1, 1, 1,
753  3, 1, 3, 1,
754  1, 13,
755  1, 13,
756  1, 13,
757  1, 13,
758  2, 2, 2,
759  2, 2, 2,
760  0,
761  2, 2, 2,
762  2, 2, 2,
763  2, 2, 2,
764  2, 2, 2,
765  2, 2, 2,
766  2, 2, 2,
767  2, 2, 2,
768  2, 2, 2,
769  2, 2, 2,
770  2, 2, 2,
771  2, 2, 2,
772  2, 2, 2,
773  2, 2, 2,
774  2, 2, 2,
775  };
776 
778 const int webpbn27[]=
779  { 27, 23,
780  // Column constraints
781  2, 4, 12,
782  3, 6, 1, 1,
783  3, 8, 1, 1,
784  5, 3, 2, 2, 1, 1,
785  6, 2, 1, 1, 2, 1, 6,
786  4, 1, 1, 1, 1,
787  6, 3, 1, 1, 2, 1, 1,
788  5, 3, 2, 3, 1, 1,
789  3, 10, 1, 1,
790  5, 4, 2, 2, 1, 1,
791  6, 3, 1, 1, 2, 1, 1,
792  4, 2, 1, 1, 1,
793  6, 3, 1, 1, 2, 1, 1,
794  5, 3, 2, 3, 1, 6,
795  3, 10, 1, 1,
796  5, 4, 2, 2, 1, 1,
797  6, 3, 1, 1, 2, 1, 1,
798  4, 1, 1, 1, 9,
799  6, 2, 1, 1, 2, 1, 1,
800  5, 2, 2, 3, 1, 3,
801  3, 8, 1, 5,
802  3, 6, 1, 1,
803  3, 4, 9, 1,
804  2, 1, 1,
805  2, 2, 1,
806  2, 1, 1,
807  1, 4,
808  // Row constraints
809  1, 11,
810  1, 17,
811  4, 3, 5, 5, 3,
812  4, 2, 2, 2, 1,
813  7, 2, 1, 3, 1, 3, 1, 4,
814  4, 3, 3, 3, 3,
815  7, 5, 1, 3, 1, 3, 1, 3,
816  4, 3, 2, 2, 4,
817  4, 5, 5, 5, 5,
818  1, 23,
819  0,
820  1, 23,
821  2, 1, 1,
822  2, 1, 1,
823  3, 1, 2, 1,
824  4, 1, 1, 1, 1,
825  4, 1, 1, 1, 1,
826  5, 1, 10, 1, 2, 1,
827  7, 1, 1, 1, 1, 1, 1, 3,
828  8, 1, 1, 1, 1, 1, 1, 1, 1,
829  7, 1, 1, 1, 1, 1, 1, 1,
830  6, 1, 1, 1, 1, 2, 2,
831  3, 5, 5, 3,
832  };
833 
835  const int webpbn1[]=
836  { 5, 10,
837  // Column constraints
838  2, 2, 1,
839  3, 2, 1, 3,
840  1, 7,
841  2, 1, 3,
842  2, 2, 1,
843  // Row constraints
844  1, 2,
845  2, 2, 1,
846  2, 1, 1,
847  1, 3,
848  2, 1, 1,
849  2, 1, 1,
850  1, 2,
851  2, 1, 1,
852  2, 1, 2,
853  1, 2,
854  };
855 
857  const int webpbn6[]=
858  { 20, 20,
859  // Column constraints
860  1, 5,
861  2, 5, 3,
862  3, 2, 3, 4,
863  3, 1, 7, 2,
864  1, 8,
865  1, 9,
866  1, 9,
867  1, 8,
868  1, 7,
869  1, 8,
870  1, 9,
871  1, 10,
872  1, 13,
873  2, 6, 2,
874  1, 4,
875  1, 6,
876  1, 6,
877  1, 5,
878  1, 6,
879  1, 6,
880  // Row constraints
881  1, 2,
882  1, 2,
883  1, 1,
884  1, 1,
885  2, 1, 3,
886  2, 2, 5,
887  4, 1, 7, 1, 1,
888  4, 1, 8, 2, 2,
889  3, 1, 9, 5,
890  2, 2, 16,
891  2, 1, 17,
892  2, 7, 11,
893  3, 5, 5, 3,
894  2, 5, 4,
895  2, 3, 3,
896  2, 2, 2,
897  2, 2, 1,
898  2, 1, 1,
899  2, 2, 2,
900  2, 2, 2,
901  };
902 
904  const int webpbn23[]=
905  { 10, 11,
906  // Column constraints
907  1, 1,
908  1, 3,
909  1, 1,
910  2, 2, 2,
911  1, 2,
912  1, 4,
913  1, 1,
914  1, 3,
915  1, 3,
916  1, 1,
917  // Row constraints
918  1, 1,
919  1, 3,
920  1, 1,
921  1, 2,
922  1, 1,
923  1, 3,
924  1, 3,
925  1, 1,
926  1, 2,
927  1, 2,
928  1, 4,
929  };
930 
932 const int webpbn16[]=
933  { 34, 34,
934  // Column constraints
935  2, 1, 1,
936  2, 2, 2,
937  2, 3, 3,
938  4, 2, 1, 1, 2,
939  4, 2, 1, 1, 2,
940  4, 1, 1, 1, 1,
941  4, 1, 1, 1, 1,
942  1, 18,
943  6, 2, 1, 1, 1, 1, 2,
944  6, 1, 1, 1, 1, 1, 1,
945  6, 1, 1, 1, 1, 1, 1,
946  1, 26,
947  8, 2, 1, 1, 1, 1, 1, 1, 2,
948  8, 2, 1, 1, 2, 2, 1, 1, 2,
949  8, 2, 1, 1, 2, 2, 1, 1, 2,
950  2, 14, 14,
951  4, 1, 1, 1, 1,
952  4, 1, 1, 1, 1,
953  2, 14, 14,
954  8, 2, 1, 1, 2, 2, 1, 1, 2,
955  8, 2, 1, 1, 2, 2, 1, 1, 2,
956  8, 2, 1, 1, 1, 1, 1, 1, 2,
957  1, 26,
958  6, 1, 1, 1, 1, 1, 1,
959  6, 1, 1, 1, 1, 1, 1,
960  6, 2, 1, 1, 1, 1, 2,
961  1, 18,
962  4, 1, 1, 1, 1,
963  4, 1, 1, 1, 1,
964  4, 2, 1, 1, 2,
965  4, 2, 1, 1, 2,
966  2, 3, 3,
967  2, 2, 2,
968  2, 1, 1,
969  // Row constraints
970  2, 1, 1,
971  2, 2, 2,
972  2, 3, 3,
973  4, 2, 1, 1, 2,
974  4, 2, 1, 1, 2,
975  4, 1, 1, 1, 1,
976  4, 1, 1, 1, 1,
977  1, 18,
978  6, 2, 1, 1, 1, 1, 2,
979  6, 1, 1, 1, 1, 1, 1,
980  6, 1, 1, 1, 1, 1, 1,
981  1, 26,
982  8, 2, 1, 1, 1, 1, 1, 1, 2,
983  8, 2, 1, 1, 2, 2, 1, 1, 2,
984  8, 2, 1, 1, 2, 2, 1, 1, 2,
985  2, 14, 14,
986  4, 1, 1, 1, 1,
987  4, 1, 1, 1, 1,
988  2, 14, 14,
989  8, 2, 1, 1, 2, 2, 1, 1, 2,
990  8, 2, 1, 1, 2, 2, 1, 1, 2,
991  8, 2, 1, 1, 1, 1, 1, 1, 2,
992  1, 26,
993  6, 1, 1, 1, 1, 1, 1,
994  6, 1, 1, 1, 1, 1, 1,
995  6, 2, 1, 1, 1, 1, 2,
996  1, 18,
997  4, 1, 1, 1, 1,
998  4, 1, 1, 1, 1,
999  4, 2, 1, 1, 2,
1000  4, 2, 1, 1, 2,
1001  2, 3, 3,
1002  2, 2, 2,
1003  2, 1, 1,
1004  };
1005 
1007  const int webpbn529[]=
1008  { 45, 45,
1009  // Column constraints
1010  6, 7, 1, 1, 1, 1, 1,
1011  13, 2, 2, 4, 1, 4, 1, 5, 1, 4, 1, 4, 1, 2,
1012  10, 3, 1, 4, 1, 4, 1, 14, 4, 1, 2,
1013  8, 1, 1, 5, 1, 2, 3, 4, 1,
1014  4, 3, 13, 1, 10,
1015  3, 1, 9, 4,
1016  4, 6, 7, 2, 2,
1017  4, 8, 4, 1, 4,
1018  6, 2, 8, 3, 2, 5, 3,
1019  5, 10, 1, 3, 7, 2,
1020  6, 8, 6, 2, 8, 1, 2,
1021  7, 1, 1, 2, 2, 8, 1, 1,
1022  11, 2, 1, 1, 1, 2, 1, 3, 1, 3, 3, 1,
1023  8, 2, 1, 1, 1, 5, 4, 2, 1,
1024  8, 2, 1, 1, 1, 1, 7, 2, 1,
1025  8, 2, 1, 1, 2, 9, 1, 2, 1,
1026  5, 4, 6, 12, 1, 3,
1027  4, 16, 13, 3, 2,
1028  3, 12, 21, 2,
1029  3, 2, 13, 23,
1030  3, 2, 14, 19,
1031  4, 2, 14, 20, 2,
1032  6, 2, 13, 7, 2, 8, 2,
1033  5, 12, 8, 1, 7, 2,
1034  9, 5, 1, 1, 1, 2, 8, 1, 5, 2,
1035  8, 2, 1, 1, 1, 9, 1, 1, 4,
1036  8, 2, 1, 1, 1, 6, 1, 3, 5,
1037  6, 2, 2, 1, 5, 6, 2,
1038  8, 2, 1, 3, 1, 3, 7, 3, 2,
1039  9, 2, 3, 2, 1, 1, 2, 4, 4, 2,
1040  9, 2, 2, 1, 1, 2, 3, 1, 8, 2,
1041  5, 9, 3, 1, 7, 2,
1042  5, 12, 4, 1, 6, 2,
1043  5, 7, 4, 1, 2, 5,
1044  5, 2, 6, 6, 5, 6,
1045  4, 8, 8, 6, 3,
1046  5, 3, 10, 8, 4, 2,
1047  5, 5, 11, 9, 5, 2,
1048  5, 3, 1, 12, 16, 2,
1049  4, 3, 1, 12, 16,
1050  4, 5, 2, 13, 21,
1051  6, 6, 1, 3, 3, 1, 1,
1052  14, 5, 1, 3, 1, 3, 1, 1, 2, 1, 4, 1, 3, 1, 3,
1053  13, 5, 1, 3, 1, 3, 1, 4, 1, 4, 1, 3, 1, 3,
1054  6, 1, 1, 1, 1, 1, 1,
1055  // Row constraints
1056  6, 7, 1, 1, 1, 1, 1,
1057  13, 3, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2,
1058  14, 1, 1, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2,
1059  9, 2, 1, 2, 1, 1, 1, 1, 6, 2,
1060  4, 3, 30, 1, 5,
1061  9, 1, 5, 8, 1, 1, 7, 1, 1, 3,
1062  7, 3, 4, 8, 1, 5, 1, 2,
1063  4, 3, 20, 6, 6,
1064  6, 3, 3, 7, 2, 5, 1,
1065  9, 3, 3, 1, 1, 9, 1, 1, 5, 6,
1066  7, 2, 3, 8, 1, 3, 4, 2,
1067  7, 5, 3, 1, 10, 4, 5, 2,
1068  6, 1, 2, 3, 8, 4, 6,
1069  5, 2, 2, 3, 11, 10,
1070  5, 2, 2, 3, 10, 7,
1071  6, 2, 3, 1, 7, 12, 2,
1072  6, 2, 3, 1, 4, 11, 2,
1073  6, 4, 1, 2, 1, 11, 2,
1074  4, 9, 1, 2, 9,
1075  5, 6, 2, 1, 4, 11,
1076  6, 2, 5, 1, 2, 6, 6,
1077  5, 6, 2, 4, 8, 4,
1078  4, 4, 2, 16, 1,
1079  4, 2, 2, 15, 2,
1080  4, 3, 2, 15, 4,
1081  4, 3, 3, 13, 4,
1082  3, 4, 12, 9,
1083  3, 1, 9, 10,
1084  5, 2, 1, 17, 7, 2,
1085  6, 2, 2, 8, 3, 8, 2,
1086  6, 2, 3, 6, 3, 8, 2,
1087  6, 2, 4, 5, 4, 7, 2,
1088  5, 2, 5, 5, 4, 6,
1089  5, 4, 4, 5, 4, 9,
1090  5, 1, 4, 6, 4, 4,
1091  6, 4, 3, 6, 4, 3, 2,
1092  7, 2, 1, 2, 7, 4, 4, 2,
1093  7, 2, 2, 2, 9, 5, 5, 2,
1094  6, 2, 2, 2, 10, 6, 6,
1095  5, 3, 2, 1, 9, 18,
1096  3, 8, 4, 23,
1097  9, 1, 2, 1, 2, 2, 1, 1, 1, 2,
1098  12, 2, 1, 4, 2, 1, 4, 1, 5, 1, 3, 1, 2,
1099  11, 2, 1, 5, 4, 4, 1, 5, 1, 3, 1, 2,
1100  5, 1, 10, 1, 1, 1,
1101  };
1102 
1103 
1105  const int webpbn65[]=
1106  { 34, 40,
1107  // Column constraints
1108  1, 5,
1109  3, 3, 2, 1,
1110  4, 3, 2, 2, 1,
1111  5, 3, 2, 2, 2, 2,
1112  6, 3, 2, 2, 2, 2, 3,
1113  7, 1, 2, 2, 2, 2, 2, 16,
1114  9, 1, 2, 2, 2, 2, 2, 2, 1, 2,
1115  9, 1, 2, 2, 2, 2, 2, 2, 13, 1,
1116  10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1,
1117  9, 6, 5, 2, 2, 2, 2, 6, 1, 1,
1118  11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1,
1119  12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1,
1120  11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1,
1121  6, 1, 7, 2, 16, 1, 1,
1122  11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1123  11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1,
1124  9, 2, 7, 1, 1, 11, 1, 1, 1, 1,
1125  9, 2, 7, 1, 1, 11, 1, 1, 1, 1,
1126  11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1,
1127  11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1128  6, 1, 7, 2, 16, 1, 1,
1129  11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1,
1130  12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1,
1131  11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1,
1132  9, 6, 5, 2, 2, 2, 2, 6, 1, 1,
1133  10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1,
1134  9, 1, 2, 2, 2, 2, 2, 2, 13, 1,
1135  9, 1, 2, 2, 2, 2, 2, 2, 1, 2,
1136  7, 1, 2, 2, 2, 2, 2, 16,
1137  6, 3, 2, 2, 2, 2, 3,
1138  5, 3, 2, 2, 2, 2,
1139  4, 3, 2, 2, 1,
1140  3, 3, 2, 1,
1141  1, 5,
1142  // Row constraints
1143  1, 12,
1144  3, 5, 2, 5,
1145  4, 5, 2, 2, 5,
1146  7, 1, 2, 2, 2, 2, 2, 1,
1147  7, 4, 2, 2, 4, 2, 2, 4,
1148  7, 4, 2, 2, 4, 2, 2, 4,
1149  7, 1, 2, 2, 2, 2, 2, 1,
1150  7, 6, 2, 2, 2, 2, 2, 6,
1151  7, 6, 2, 2, 2, 2, 2, 6,
1152  3, 1, 14, 1,
1153  2, 10, 10,
1154  4, 8, 3, 3, 8,
1155  8, 1, 1, 2, 1, 1, 2, 1, 1,
1156  6, 9, 2, 2, 2, 2, 9,
1157  2, 9, 9,
1158  6, 1, 1, 1, 1, 1, 1,
1159  3, 12, 2, 12,
1160  2, 12, 12,
1161  5, 1, 1, 4, 1, 1,
1162  2, 14, 14,
1163  2, 12, 12,
1164  5, 2, 1, 4, 1, 2,
1165  3, 9, 4, 9,
1166  5, 1, 7, 4, 7, 1,
1167  7, 1, 1, 1, 4, 1, 1, 1,
1168  5, 1, 7, 4, 7, 1,
1169  5, 1, 7, 4, 7, 1,
1170  7, 1, 2, 1, 2, 1, 2, 1,
1171  5, 1, 7, 2, 7, 1,
1172  7, 1, 1, 6, 2, 6, 1, 1,
1173  9, 1, 1, 1, 1, 2, 1, 1, 1, 1,
1174  7, 1, 1, 6, 2, 6, 1, 1,
1175  6, 1, 1, 5, 5, 1, 1,
1176  7, 1, 1, 1, 8, 1, 1, 1,
1177  6, 1, 1, 4, 4, 1, 1,
1178  5, 1, 2, 6, 2, 1,
1179  4, 2, 4, 4, 2,
1180  3, 2, 6, 2,
1181  2, 4, 4,
1182  1, 6,
1183  };
1184 
1185 
1186  const int *specs[] = {heart, bear, crocodile, unknown,
1187  pinwheel, difficult, non_unique, dragonfly,
1188  castle, p200,
1189  // From the webpbn survey
1190  webpbn1, // 10
1191  webpbn6, // 11
1192  webpbn21, // 12
1193  webpbn27, // 13
1194  webpbn23, // 14
1195  webpbn16, // 15
1196  webpbn529, // 16
1197  webpbn65, // 17
1198  webpbn436, // 18
1199  };
1200  const unsigned n_examples = sizeof(specs)/sizeof(int*);
1202 
1203 }
1204 
1205 // STATISTICS: example-any
const int * spec
Specification to be used.
Definition: nonogram.cpp:70
unsigned int size(I &i)
Size of all ranges of range iterator i.
int height(void) const
Return height of board.
Definition: nonogram.cpp:79
Slice< A > row(int r) const
Access row r.
Definition: matrix.hpp:177
Computation spaces.
Definition: core.hpp:1742
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:39
Regular expressions over integer values.
Definition: minimodel.hh:1625
DFA line(int &spos)
Returns next regular expression for line starting from spos.
Definition: nonogram.cpp:84
Example: Nonogram
Definition: nonogram.cpp:67
Gecode toplevel namespace
@ BRANCH_AFC
Use AFC for branching.
Definition: nonogram.cpp:103
Boolean variable array.
Definition: int.hh:808
Options opt
The options.
Definition: test.cpp:97
Parametric base-class for scripts.
Definition: driver.hh:729
int main(int argc, char *argv[])
Main-function.
Definition: nonogram.cpp:199
void branching(int v)
Set default branching value.
Definition: options.hpp:225
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:548
virtual Space * copy(void)
Copy space during cloning.
Definition: nonogram.cpp:176
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition: val.hpp:135
@ BRANCH_NONE
Branch on rows/columns in order.
Definition: nonogram.cpp:102
BoolVarBranch BOOL_VAR_AFC_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count with decay factor d.
Definition: var.hpp:404
Matrix-interface for arrays.
Definition: minimodel.hh:2087
Deterministic finite automaton (DFA)
Definition: int.hh:2049
Nonogram(const SizeOptions &opt)
Construction of the model.
Definition: nonogram.cpp:107
Slice< A > col(int c) const
Access column c.
Definition: matrix.hpp:183
int width(void) const
Return width of board.
Definition: nonogram.cpp:75
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
virtual void print(std::ostream &os) const
Print solution.
Definition: nonogram.cpp:182
BoolVarArray b
Fields of board.
Definition: nonogram.cpp:72
Gecode::IntArgs i({1, 2, 3, 4})
Nonogram(Nonogram &s)
Constructor for cloning s.
Definition: nonogram.cpp:170
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:364
Options for scripts with additional size parameter
Definition: driver.hh:675