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