43 using namespace Gecode;
48 extern const int* specs[];
50 extern const unsigned int n_examples;
56 bool operator<(
const Slack& rhs)
const {
return slack < rhs.slack; }
98 int hints = spec[spos++];
101 r += r1(spec[spos],spec[spos]);
103 for (
int i=hints-1;
i--; spos++)
104 r += between + r1(spec[spos],spec[spos]);
118 : spec(specs[opt.
size()]),
b(*this,width()*height(),0,1) {
124 for (
int w=0; w<width(); w++)
127 for (
int h=0; h<height(); h++)
150 for (
int w=0; w<width(); w++) {
151 int hint = spec[spos++];
152 cols += hint; spos += hint;
154 for (
int h=0; h<height(); h++) {
155 int hint = spec[spos++];
156 rows += hint; spos += hint;
159 if (rows*width() > cols*height()) {
160 for (
int w=0; w<width(); w++)
163 for (
int h=0; h<height(); h++)
194 for (
int h = 0; h < height(); ++h) {
196 for (
int w = 0; w < width(); ++w)
197 os << ((
m(w,h).val() == 1) ?
'#' :
' ');
214 "Branch on rows/columns in order");
216 "Use AFC for branching");
217 opt.
parse(argc,argv);
218 if (opt.
size() >= n_examples) {
219 std::cerr <<
"Error: size must be between 0 and "
220 << n_examples-1 << std::endl;
223 Script::run<Nonogram,DFS,SizeOptions>(
opt);
294 const int crocodile[] =
325 const int unknown[] =
352 const int pinwheel[] =
371 const int difficult[] =
408 const int non_unique[] =
445 const int dragonfly[] =
492 const int castle[] = {
498 10, 2,4,2,1,1,1,4,1,1,2,
501 9, 3,3,3,1,1,6,1,1,1,
502 9, 3,2,2,2,2,8,1,1,3,
540 10, 1,1,4,2,1,1,1,1,1,4,
550 9, 1,2,2,2,2,4,1,1,3,
561 13, 2,2,4,9,1,5,1,1,1,1,1,1,1,
565 12, 4,5,3,14,1,1,1,1,4,1,1,3,
566 19, 3,3,2,2,2,4,1,1,1,1,1,1,1,1,3,1,1,3,2,
567 11, 8,2,7,2,1,1,2,1,1,3,3,
568 13, 1,5,9,12,2,1,1,3,1,1,2,2,1,
569 17, 3,2,2,1,1,1,1,4,1,1,1,3,3,1,1,2,2,
570 12, 5,2,2,2,2,1,5,2,1,1,2,5,
571 12, 3,5,9,2,1,1,6,3,1,3,2,3,
572 12, 1,4,1,1,1,4,1,5,5,3,3,3,
573 10, 4,1,1,1,1,3,4,6,6,3,
574 12, 3,1,3,1,1,3,3,1,1,4,6,1,
575 11, 3,1,5,1,1,3,1,1,9,4,1,
576 14, 2,1,1,7,1,4,1,1,1,1,1,1,3,5,
577 11, 9,2,1,3,1,1,1,1,4,2,1,
578 10, 1,14,1,1,2,2,2,10,1,2,
579 10, 1,9,2,1,2,6,1,5,3,2,
580 12, 1,9,9,1,2,2,3,1,1,4,3,1,
581 10, 10,1,3,4,1,3,2,1,2,8,
582 9, 9,1,3,5,1,1,1,2,7,
583 12, 4,5,1,2,5,1,3,1,1,2,1,3,
584 14, 1,1,1,1,2,6,2,3,2,1,1,2,3,1,
585 11, 1,6,1,5,7,1,3,3,2,4,3,
586 10, 1,2,1,2,9,1,5,2,6,2,
587 8, 10,2,2,13,1,3,3,1,
588 11, 2,2,1,6,2,3,3,2,2,2,1,
589 12, 2,2,1,1,12,2,2,9,2,2,2,2,
590 9, 5,1,2,4,1,5,11,2,2,
660 const int webpbn436[]=
676 6, 12, 2, 3, 2, 3, 2,
686 7, 6, 2, 2, 2, 2, 2, 2,
711 7, 4, 2, 2, 2, 2, 3, 1,
712 7, 3, 1, 2, 2, 2, 3, 3,
713 7, 3, 2, 2, 2, 2, 2, 4,
721 7, 10, 2, 2, 2, 2, 2, 10,
722 9, 4, 2, 3, 3, 2, 2, 3, 2, 5,
742 const int webpbn21[]=
788 const int webpbn27[]=
823 7, 2, 1, 3, 1, 3, 1, 4,
825 7, 5, 1, 3, 1, 3, 1, 3,
837 7, 1, 1, 1, 1, 1, 1, 3,
838 8, 1, 1, 1, 1, 1, 1, 1, 1,
839 7, 1, 1, 1, 1, 1, 1, 1,
914 const int webpbn23[]=
942 const int webpbn16[]=
957 8, 2, 1, 1, 1, 1, 1, 1, 2,
958 8, 2, 1, 1, 2, 2, 1, 1, 2,
959 8, 2, 1, 1, 2, 2, 1, 1, 2,
964 8, 2, 1, 1, 2, 2, 1, 1, 2,
965 8, 2, 1, 1, 2, 2, 1, 1, 2,
966 8, 2, 1, 1, 1, 1, 1, 1, 2,
992 8, 2, 1, 1, 1, 1, 1, 1, 2,
993 8, 2, 1, 1, 2, 2, 1, 1, 2,
994 8, 2, 1, 1, 2, 2, 1, 1, 2,
999 8, 2, 1, 1, 2, 2, 1, 1, 2,
1000 8, 2, 1, 1, 2, 2, 1, 1, 2,
1001 8, 2, 1, 1, 1, 1, 1, 1, 2,
1003 6, 1, 1, 1, 1, 1, 1,
1004 6, 1, 1, 1, 1, 1, 1,
1005 6, 2, 1, 1, 1, 1, 2,
1017 const int webpbn529[]=
1020 6, 7, 1, 1, 1, 1, 1,
1021 13, 2, 2, 4, 1, 4, 1, 5, 1, 4, 1, 4, 1, 2,
1022 10, 3, 1, 4, 1, 4, 1, 14, 4, 1, 2,
1023 8, 1, 1, 5, 1, 2, 3, 4, 1,
1028 6, 2, 8, 3, 2, 5, 3,
1030 6, 8, 6, 2, 8, 1, 2,
1031 7, 1, 1, 2, 2, 8, 1, 1,
1032 11, 2, 1, 1, 1, 2, 1, 3, 1, 3, 3, 1,
1033 8, 2, 1, 1, 1, 5, 4, 2, 1,
1034 8, 2, 1, 1, 1, 1, 7, 2, 1,
1035 8, 2, 1, 1, 2, 9, 1, 2, 1,
1042 6, 2, 13, 7, 2, 8, 2,
1044 9, 5, 1, 1, 1, 2, 8, 1, 5, 2,
1045 8, 2, 1, 1, 1, 9, 1, 1, 4,
1046 8, 2, 1, 1, 1, 6, 1, 3, 5,
1047 6, 2, 2, 1, 5, 6, 2,
1048 8, 2, 1, 3, 1, 3, 7, 3, 2,
1049 9, 2, 3, 2, 1, 1, 2, 4, 4, 2,
1050 9, 2, 2, 1, 1, 2, 3, 1, 8, 2,
1061 6, 6, 1, 3, 3, 1, 1,
1062 14, 5, 1, 3, 1, 3, 1, 1, 2, 1, 4, 1, 3, 1, 3,
1063 13, 5, 1, 3, 1, 3, 1, 4, 1, 4, 1, 3, 1, 3,
1064 6, 1, 1, 1, 1, 1, 1,
1066 6, 7, 1, 1, 1, 1, 1,
1067 13, 3, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2,
1068 14, 1, 1, 1, 3, 1, 4, 1, 4, 1, 5, 1, 5, 1, 2,
1069 9, 2, 1, 2, 1, 1, 1, 1, 6, 2,
1071 9, 1, 5, 8, 1, 1, 7, 1, 1, 3,
1072 7, 3, 4, 8, 1, 5, 1, 2,
1074 6, 3, 3, 7, 2, 5, 1,
1075 9, 3, 3, 1, 1, 9, 1, 1, 5, 6,
1076 7, 2, 3, 8, 1, 3, 4, 2,
1077 7, 5, 3, 1, 10, 4, 5, 2,
1078 6, 1, 2, 3, 8, 4, 6,
1081 6, 2, 3, 1, 7, 12, 2,
1082 6, 2, 3, 1, 4, 11, 2,
1083 6, 4, 1, 2, 1, 11, 2,
1086 6, 2, 5, 1, 2, 6, 6,
1095 6, 2, 2, 8, 3, 8, 2,
1096 6, 2, 3, 6, 3, 8, 2,
1097 6, 2, 4, 5, 4, 7, 2,
1101 6, 4, 3, 6, 4, 3, 2,
1102 7, 2, 1, 2, 7, 4, 4, 2,
1103 7, 2, 2, 2, 9, 5, 5, 2,
1104 6, 2, 2, 2, 10, 6, 6,
1107 9, 1, 2, 1, 2, 2, 1, 1, 1, 2,
1108 12, 2, 1, 4, 2, 1, 4, 1, 5, 1, 3, 1, 2,
1109 11, 2, 1, 5, 4, 4, 1, 5, 1, 3, 1, 2,
1115 const int webpbn65[]=
1122 6, 3, 2, 2, 2, 2, 3,
1123 7, 1, 2, 2, 2, 2, 2, 16,
1124 9, 1, 2, 2, 2, 2, 2, 2, 1, 2,
1125 9, 1, 2, 2, 2, 2, 2, 2, 13, 1,
1126 10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1,
1127 9, 6, 5, 2, 2, 2, 2, 6, 1, 1,
1128 11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1,
1129 12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1,
1130 11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1,
1131 6, 1, 7, 2, 16, 1, 1,
1132 11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1133 11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1,
1134 9, 2, 7, 1, 1, 11, 1, 1, 1, 1,
1135 9, 2, 7, 1, 1, 11, 1, 1, 1, 1,
1136 11, 1, 2, 1, 3, 1, 1, 6, 1, 1, 1, 1,
1137 11, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1138 6, 1, 7, 2, 16, 1, 1,
1139 11, 6, 1, 2, 3, 2, 2, 2, 2, 1, 1, 1,
1140 12, 3, 4, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1,
1141 11, 1, 7, 3, 2, 2, 2, 2, 2, 1, 1, 1,
1142 9, 6, 5, 2, 2, 2, 2, 6, 1, 1,
1143 10, 3, 2, 2, 2, 2, 2, 2, 4, 1, 1,
1144 9, 1, 2, 2, 2, 2, 2, 2, 13, 1,
1145 9, 1, 2, 2, 2, 2, 2, 2, 1, 2,
1146 7, 1, 2, 2, 2, 2, 2, 16,
1147 6, 3, 2, 2, 2, 2, 3,
1156 7, 1, 2, 2, 2, 2, 2, 1,
1157 7, 4, 2, 2, 4, 2, 2, 4,
1158 7, 4, 2, 2, 4, 2, 2, 4,
1159 7, 1, 2, 2, 2, 2, 2, 1,
1160 7, 6, 2, 2, 2, 2, 2, 6,
1161 7, 6, 2, 2, 2, 2, 2, 6,
1165 8, 1, 1, 2, 1, 1, 2, 1, 1,
1166 6, 9, 2, 2, 2, 2, 9,
1168 6, 1, 1, 1, 1, 1, 1,
1177 7, 1, 1, 1, 4, 1, 1, 1,
1180 7, 1, 2, 1, 2, 1, 2, 1,
1182 7, 1, 1, 6, 2, 6, 1, 1,
1183 9, 1, 1, 1, 1, 2, 1, 1, 1, 1,
1184 7, 1, 1, 6, 2, 6, 1, 1,
1185 6, 1, 1, 5, 5, 1, 1,
1186 7, 1, 1, 1, 8, 1, 1, 1,
1187 6, 1, 1, 4, 4, 1, 1,
1196 const int *specs[] = {heart, bear, crocodile, unknown,
1197 pinwheel, difficult, non_unique, dragonfly,
1210 const unsigned n_examples =
sizeof(specs)/
sizeof(
int*);