48 extern const int* specs[];
50 extern const unsigned int n_examples;
92 int hints = spec[spos++];
95 r += r1(spec[spos],spec[spos]);
97 for (
int i=hints-1;
i--; spos++)
98 r += between + r1(spec[spos],spec[spos]);
112 : spec(specs[opt.
size()]), b(*this,width()*height(),0,1) {
118 for (
int w=0; w<width(); w++)
121 for (
int h=0; h<height(); h++)
144 for (
int w=0; w<width(); w++) {
145 int hint = spec[spos++];
146 cols += hint; spos += hint;
148 for (
int h=0; h<height(); h++) {
149 int hint = spec[spos++];
150 rows += hint; spos += hint;
153 if (rows*width() > cols*height()) {
154 for (
int w=0; w<width(); w++)
157 for (
int h=0; h<height(); h++)
188 for (
int h = 0; h < height(); ++h) {
190 for (
int w = 0; w < width(); ++w)
191 os << ((m(w,h).val() == 1) ?
'#' :
' ');
208 "Branch on rows/columns in order");
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;
217 Script::run<Nonogram,DFS,SizeOptions>(
opt);
288 const int crocodile[] =
319 const int unknown[] =
346 const int pinwheel[] =
365 const int difficult[] =
402 const int non_unique[] =
439 const int dragonfly[] =
486 const int castle[] = {
492 10, 2,4,2,1,1,1,4,1,1,2,
495 9, 3,3,3,1,1,6,1,1,1,
496 9, 3,2,2,2,2,8,1,1,3,
534 10, 1,1,4,2,1,1,1,1,1,4,
544 9, 1,2,2,2,2,4,1,1,3,
555 13, 2,2,4,9,1,5,1,1,1,1,1,1,1,
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,
654 const int webpbn436[]=
670 6, 12, 2, 3, 2, 3, 2,
680 7, 6, 2, 2, 2, 2, 2, 2,
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,
715 7, 10, 2, 2, 2, 2, 2, 10,
716 9, 4, 2, 3, 3, 2, 2, 3, 2, 5,
736 const int webpbn21[]=
782 const int webpbn27[]=
817 7, 2, 1, 3, 1, 3, 1, 4,
819 7, 5, 1, 3, 1, 3, 1, 3,
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,
908 const int webpbn23[]=
936 const int webpbn16[]=
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,
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,
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,
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,
1011 const int webpbn529[]=
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,
1022 6, 2, 8, 3, 2, 5, 3,
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,
1036 6, 2, 13, 7, 2, 8, 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,
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,
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,
1065 9, 1, 5, 8, 1, 1, 7, 1, 1, 3,
1066 7, 3, 4, 8, 1, 5, 1, 2,
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,
1075 6, 2, 3, 1, 7, 12, 2,
1076 6, 2, 3, 1, 4, 11, 2,
1077 6, 4, 1, 2, 1, 11, 2,
1080 6, 2, 5, 1, 2, 6, 6,
1089 6, 2, 2, 8, 3, 8, 2,
1090 6, 2, 3, 6, 3, 8, 2,
1091 6, 2, 4, 5, 4, 7, 2,
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,
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,
1109 const int webpbn65[]=
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,
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,
1159 8, 1, 1, 2, 1, 1, 2, 1, 1,
1160 6, 9, 2, 2, 2, 2, 9,
1162 6, 1, 1, 1, 1, 1, 1,
1171 7, 1, 1, 1, 4, 1, 1, 1,
1174 7, 1, 2, 1, 2, 1, 2, 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,
1190 const int *specs[] = {heart, bear, crocodile, unknown,
1191 pinwheel, difficult, non_unique, dragonfly,
1204 const unsigned n_examples =
sizeof(specs)/
sizeof(
int*);
void size(unsigned int s)
Set default size.
Options for scripts with additional size parameter
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Regular expressions over integer values.
const int * spec
Specification to be used.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Nonogram(bool share, Nonogram &s)
Constructor for cloning s.
Parametric base-class for scripts.
void decay(double d)
Set default decay factor.
int width(void) const
Return width of board.
Branch on rows/columns in order.
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Deterministic finite automaton (DFA)
IntVarBranch INT_VAR_AFC_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count with decay factor d.
Gecode::IntArgs i(4, 1, 2, 3, 4)
virtual Space * copy(bool share)
Copy space during cloning.
int height(void) const
Return height of board.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Slice< A > row(int r) const
Access row r.
void branching(int v)
Set default branching value.
int main(int argc, char *argv[])
Main-function.
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntConLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
IntValBranch INT_VAL_MAX(void)
Select largest value.
DFA line(int &spos)
Returns next regular expression for line starting from spos.
Nonogram(const SizeOptions &opt)
Construction of the model.
Matrix-interface for arrays.
BoolVarArray b
Fields of board.
virtual void print(std::ostream &os) const
Print solution.
Gecode toplevel namespace
Slice< A > col(int c) const
Access column c.
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.