00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041
00042 using namespace Gecode;
00043
00044 namespace {
00045
00066
00067
00068 const int k0[] = {
00069
00070 12,10,
00071
00072 2, 0, 5,16, 3, 0, 2, 4, 5, 0, 3, 6, 6, 0, 2, 4,
00073 7, 0, 5,15, 10, 0, 3, 6, 11, 0, 3, 7, 1, 1, 3, 7,
00074 9, 1, 5,16, 4, 2, 2, 5, 8, 2, 2, 3, 3, 3, 5,16,
00075 6, 3, 3, 8, 5, 4, 5,15, 10, 4, 5,15, 4, 5, 2, 3,
00076 8, 5, 2, 4, 11, 5, 3, 7, 1, 6, 3, 6, 2, 6, 3, 7,
00077 7, 6, 3, 7, 6, 7, 2, 3, 9, 7, 2, 4, -1,
00078
00079 1, 1, 2, 7, 4, 1, 3, 9, 9, 1, 2, 4, 0, 2, 3, 7,
00080 4, 2, 3, 7, 8, 2, 3, 6, 0, 3, 2, 3, 3, 3, 2, 4,
00081 6, 3, 5,16, 0, 4, 4,10, 5, 4, 4,10, 1, 5, 2,10,
00082 4, 5, 3, 6, 8, 5, 2, 5, 2, 6, 4,10, 7, 6, 4,12,
00083 0, 7, 5,16, 6, 7, 2, 4, 9, 7, 2, 4, 0, 8, 3, 7,
00084 4, 8, 3, 8, 8, 8, 3, 6, 0, 9, 2, 3, 4, 9, 3, 7,
00085 8, 9, 2, 3, -1
00086 };
00087
00088
00089 const int k1[] = {
00090
00091 12,10,
00092
00093 1, 0, 2, 4, 2, 0, 5,15, 5, 0, 5,18, 6, 0, 2,12,
00094 7, 0, 3, 8, 10, 0, 3,24, 11, 0, 3,23, 3, 1, 2, 7,
00095 9, 1, 3,24, 4, 2, 5,16, 8, 2, 5,35, 1, 3, 2,12,
00096 6, 3, 3,17, 7, 4, 5,34, 10, 4, 5,34, 11, 4, 2,16,
00097 3, 5, 3, 6, 1, 6, 3, 7, 2, 6, 3, 6, 5, 6, 3,23,
00098 9, 6, 2,10, 6, 7, 2,14, 11, 7, 2,10, -1,
00099
00100 0, 1, 2, 3, 4, 1, 3,15, 9, 1, 2,16, 0, 2, 3, 6,
00101 4, 2, 3, 7, 8, 2, 3,24, 1, 3, 4,11, 6, 3, 5,34,
00102 0, 4, 2,14, 3, 4, 3,23, 7, 4, 2,14, 0, 5, 2, 7,
00103 3, 5, 5,15, 9, 5, 2,17, 2, 6, 2, 6, 5, 6, 3,23,
00104 9, 6, 2,13, 0, 7, 5,16, 6, 7, 4,30, 0, 8, 3, 6,
00105 4, 8, 3,23, 8, 8, 3, 7, 0, 9, 2, 4, 4, 9, 3,24,
00106 9, 9, 2,17, -1
00107 };
00108
00109
00110 const int k2[] = {
00111
00112 12,10,
00113
00114 2, 0, 5,15, 3, 0, 2, 3, 7, 0, 3, 7, 8, 0, 4,23,
00115 9, 0, 2,12, 10, 0, 3,20, 11, 0, 3, 9, 4, 1, 3, 7,
00116 5, 1, 4,10, 1, 2, 3, 6, 6, 2, 5,15, 9, 3, 2,16,
00117 3, 4, 2, 3, 7, 4, 4,13, 10, 4, 5,35, 11, 4, 3,23,
00118 4, 5, 4,11, 8, 5, 3,23, 1, 6, 3,23, 2, 6, 3,14,
00119 5, 6, 3,11, 3, 7, 2,13, 9, 7, 2,17, -1,
00120
00121 1, 1, 2, 4, 6, 1, 5,15, 1, 2, 4,11, 6, 2, 5,34,
00122 0, 3, 2, 3, 3, 3, 5,15, 9, 3, 2,10, 0, 4, 2, 4,
00123 3, 4, 3, 6, 7, 4, 2,17, 0, 5, 3, 7, 4, 5, 3, 8,
00124 8, 5, 3,18, 2, 6, 2, 3, 5, 6, 3,11, 9, 6, 2,16,
00125 0, 7, 2,16, 3, 7, 5,16, 9, 7, 2,17, 0, 8, 5,16,
00126 6, 8, 4,30, 0, 9, 5,35, 8, 9, 2,17, -1
00127 };
00128
00129
00130 const int k3[] = {
00131
00132 12,10,
00133
00134 3, 0, 3, 7, 4, 0, 6,21, 7, 0, 4,29, 8, 0, 2,17,
00135 10, 0, 4,29, 11, 0, 3,23, 2, 1, 3, 6, 6, 1, 2,16,
00136 9, 1, 4,14, 1, 2, 2, 4, 5, 2, 2, 3, 8, 3, 6,22,
00137 3, 4, 4,10, 2, 5, 4,11, 5, 5, 4,10, 7, 5, 2,10,
00138 10, 5, 3,24, 11, 5, 2,16, 1, 6, 3, 7, 6, 6, 2, 9,
00139 9, 6, 3,23, 4, 7, 2, 4, -1,
00140
00141 2, 1, 2, 4, 6, 1, 2,17, 9, 1, 2,16, 1, 2, 3, 6,
00142 5, 2, 6,39, 0, 3, 7,28, 8, 3, 3,24, 0, 4, 2, 3,
00143 3, 4, 2, 3, 6, 4, 4,20, 2, 5, 2, 9, 7, 5, 2, 4,
00144 1, 6, 4,10, 6, 6, 2, 3, 9, 6, 2,16, 0, 7, 3, 6,
00145 4, 7, 7,42, 0, 8, 6,21, 7, 8, 3,21, 0, 9, 2, 4,
00146 3, 9, 2, 3, 7, 9, 2,16, -1
00147 };
00148
00149
00150 const int k4[] = {
00151
00152 20,12,
00153
00154 3, 0, 3,21, 4, 0, 2, 4, 5, 0, 4,11, 8, 0, 2, 8,
00155 9, 0, 3, 7, 11, 0, 2, 3, 12, 0, 3, 6, 15, 0, 6,39,
00156 16, 0, 2, 3, 17, 0, 3,23, 2, 1, 5,15, 6, 1, 4,10,
00157 10, 1, 4,11, 14, 1, 4,11, 18, 1, 3, 6, 1, 2, 3,24,
00158 7, 2, 4,14, 13, 2, 2,10, 19, 2, 2,16, 4, 3, 5,18,
00159 8, 3, 4,10, 11, 3, 4,12, 16, 3, 5,33, 3, 4, 3,23,
00160 9, 4, 4,29, 12, 4, 4,30, 17, 4, 3,18, 5, 5, 6,38,
00161 13, 5, 4,29, 18, 5, 5,15, 6, 6, 4,25, 10, 6, 4,12,
00162 14, 6, 4,28, 19, 6, 3,21, 1, 7, 2, 4, 2, 7, 3, 7,
00163 7, 7, 2, 7, 15, 7, 4,11, 3, 8, 3,19, 8, 8, 3,24,
00164 11, 8, 3, 7, 17, 8, 3, 6, 4, 9, 2,16, 9, 9, 2,16,
00165 12, 9, 2,17, 16, 9, 2, 5, -1,
00166
00167 2, 1, 3, 7, 7, 1, 2, 4, 10, 1, 2, 4, 14, 1, 3,19,
00168 1, 2, 5,18, 7, 2, 5,15, 13, 2, 5,16, 0, 3, 3,21,
00169 4, 3, 3, 6, 8, 3, 2, 3, 11, 3, 4,11, 16, 3, 3,20,
00170 0, 4, 2,14, 3, 4, 5,15, 9, 4, 2, 3, 12, 4, 4,29,
00171 17, 4, 2, 8, 0, 5, 4,27, 5, 5, 7,42, 13, 5, 4,12,
00172 1, 6, 4,12, 6, 6, 3, 8, 10, 6, 3,20, 14, 6, 4,29,
00173 2, 7, 4,28, 7, 7, 7,28, 15, 7, 4,28, 0, 8, 2, 3,
00174 3, 8, 4,11, 8, 8, 2,10, 11, 8, 5,35, 17, 8, 2,10,
00175 0, 9, 3, 6, 4, 9, 4,30, 9, 9, 2, 3, 12, 9, 3,19,
00176 16, 9, 3, 7, 1,10, 5,34, 7,10, 5,34, 13,10, 5,17,
00177 2,11, 3,23, 7,11, 2,17, 10,11, 2,10, 14,11, 3, 6,
00178 -1
00179 };
00180
00181
00182 const int k5[] = {
00183
00184 20,12,
00185
00186 1, 0, 2, 3, 2, 0, 5,33, 4, 0, 2, 8, 5, 0, 4,14,
00187 7, 0, 5,15, 8, 0, 3,19, 9, 0, 2,12, 11, 0, 4,11,
00188 12, 0, 2, 4, 13, 0, 5,16, 15, 0, 4,11, 16, 0, 2,17,
00189 18, 0, 5,34, 19, 0, 2,17, 3, 1, 2, 3, 10, 1, 9,45,
00190 17, 1, 2,16, 6, 2, 3,20, 14, 2, 3,12, 1, 3, 2,13,
00191 4, 3, 5,33, 9, 3, 3,20, 16, 3, 5,21, 19, 3, 2, 8,
00192 3, 4, 3,11, 8, 4, 3,11, 12, 4, 3, 7, 17, 4, 3, 8,
00193 11, 5, 3,23, 1, 6, 2,11, 2, 6, 5,15, 6, 6, 3,23,
00194 7, 6, 5,27, 13, 6, 5,30, 14, 6, 3, 7, 18, 6, 5,15,
00195 19, 6, 2, 3, 5, 7, 4,26, 9, 7, 4,27, 15, 7, 4,27,
00196 3, 8, 2, 7, 12, 8, 3,24, 17, 8, 2,17, 1, 9, 2, 5,
00197 4, 9, 2, 9, 8, 9, 2, 3, 11, 9, 2,16, 16, 9, 2,16,
00198 19, 9, 2,10, -1,
00199
00200 0, 1, 2, 4, 3, 1, 2, 7, 6, 1, 3, 7, 10, 1, 3, 7,
00201 14, 1, 2,11, 17, 1, 2,16, 0, 2, 5,16, 6, 2, 7,42,
00202 14, 2, 5,35, 1, 3, 2,10, 4, 3, 4,15, 9, 3, 2, 6,
00203 12, 3, 3, 7, 16, 3, 2,13, 0, 4, 2,17, 3, 4, 4,29,
00204 8, 4, 3,19, 12, 4, 4,11, 17, 4, 2, 9, 0, 5, 4,29,
00205 5, 5, 5,33, 11, 5, 3, 6, 15, 5, 4,29, 2, 6, 2, 4,
00206 7, 6, 5,16, 15, 6, 2, 4, 0, 7, 4,12, 5, 7, 3,10,
00207 9, 7, 5,18, 15, 7, 4,12, 0, 8, 2,13, 3, 8, 4,29,
00208 8, 8, 3,24, 12, 8, 4,23, 17, 8, 2, 5, 1, 9, 2, 6,
00209 4, 9, 3,24, 8, 9, 2, 4, 11, 9, 4,28, 16, 9, 2,11,
00210 0,10, 5,15, 6,10, 7,41, 14,10, 5,34, 0,11, 2, 3,
00211 3,11, 2,17, 6,11, 3,14, 10,11, 3,23, 14,11, 2,11,
00212 17,11, 2, 4, -1
00213 };
00214
00215
00216 const int k6[] = {
00217
00218 20,12,
00219
00220 1, 0, 2, 6, 2, 0, 2,16, 4, 0, 3,10, 5, 0, 2,12,
00221 9, 0, 7,28, 10, 0, 2,12, 11, 0, 3,24, 15, 0, 3,10,
00222 16, 0, 2,17, 17, 0, 6,22, 3, 1, 3,18, 6, 1, 4,10,
00223 8, 1, 2, 8, 12, 1, 2,10, 13, 1, 3,18, 18, 1, 3,12,
00224 7, 2, 4,11, 14, 2, 3, 7, 19, 2, 2, 7, 1, 3, 2, 8,
00225 2, 3, 3, 7, 5, 3, 4,25, 10, 3, 2, 4, 16, 3, 4,15,
00226 4, 4, 4,11, 11, 4, 7,42, 12, 4, 2,17, 15, 4, 4,26,
00227 3, 5, 6,22, 8, 5, 2,16, 13, 5, 4,30, 18, 5, 3,24,
00228 6, 6, 3, 7, 10, 6, 2, 4, 14, 6, 4,29, 19, 6, 2,14,
00229 1, 7, 2,16, 2, 7, 3,11, 7, 7, 3,24, 17, 7, 3,21,
00230 5, 8, 3,23, 8, 8, 2,12, 9, 8, 3,20, 12, 8, 2,17,
00231 16, 8, 3, 6, 4, 9, 2, 9, 10, 9, 2,16, 15, 9, 2, 9,
00232 18, 9, 2, 3, 19, 9, 2,12, -1,
00233
00234 0, 1, 2,10, 3, 1, 2, 5, 8, 1, 3,23, 14, 1, 3,11,
00235 0, 2, 6,38, 7, 2, 6,39, 14, 2, 4,30, 2, 3, 2,10,
00236 5, 3, 4,11, 10, 3, 5,18, 16, 3, 3, 7, 0, 4, 3, 7,
00237 4, 4, 3, 7, 8, 4, 2, 6, 12, 4, 2, 8, 15, 4, 4,11,
00238 0, 5, 2, 8, 3, 5, 4,14, 8, 5, 4,24, 13, 5, 4,10,
00239 1, 6, 4,13, 6, 6, 3,14, 10, 6, 3,19, 14, 6, 4,29,
00240 2, 7, 4,15, 7, 7, 4,14, 12, 7, 4,29, 17, 7, 2,16,
00241 0, 8, 4,29, 5, 8, 2,13, 9, 8, 2, 8, 12, 8, 3,23,
00242 16, 8, 3,22, 0, 9, 3,10, 4, 9, 5,32, 10, 9, 4,29,
00243 15, 9, 2,10, 1,10, 4,14, 6,10, 6,39, 13,10, 6,22,
00244 2,11, 3,21, 8,11, 3,23, 14,11, 2, 6, 17,11, 2,11,
00245 -1
00246 };
00247
00248
00249 const int k7[] = {
00250
00251 22,14,
00252
00253 1, 0, 3,23, 2, 0, 4,29, 3, 0, 2,16, 7, 0, 2, 7,
00254 8, 0, 2,10, 9, 0, 5,30, 13, 0, 7,41, 14, 0, 2,16,
00255 15, 0, 4,29, 17, 0, 2, 3, 18, 0, 6,21, 20, 0, 3, 7,
00256 21, 0, 2, 4, 4, 1, 5,35, 6, 1, 2, 4, 10, 1, 2,17,
00257 12, 1, 3,24, 19, 1, 9,45, 5, 2, 3,23, 11, 2, 9,45,
00258 16, 2, 4,21, 3, 3, 9,45, 7, 3, 5,15, 8, 3, 4,10,
00259 14, 3, 2,10, 17, 3, 2, 3, 6, 4, 2, 4, 10, 4, 4,30,
00260 20, 4, 4,11, 2, 5, 4,13, 12, 5, 4,30, 15, 5, 5,35,
00261 21, 5, 2, 4, 1, 6, 2, 4, 9, 6, 7,41, 14, 6, 4,29,
00262 4, 7, 6,38, 6, 7, 4,11, 16, 7, 2,16, 18, 7, 5,15,
00263 5, 8, 2, 9, 8, 8, 2,17, 13, 8, 5,16, 17, 8, 3, 7,
00264 7, 9, 4,20, 10, 9, 3,23, 20, 9, 4,12, 2,10, 3,23,
00265 12,10, 2, 6, 16,10, 2, 4, 21,10, 3, 9, 1,11, 2,16,
00266 5,11, 2,16, 8,11, 2,16, 14,11, 2, 6, 15,11, 2, 4,
00267 19,11, 2, 4, -1,
00268
00269 0, 1, 3,23, 6, 1, 3, 8, 12, 1, 3,23, 16, 1, 2, 4,
00270 19, 1, 2, 4, 0, 2, 4,30, 5, 2, 5,31, 11, 2, 4,29,
00271 16, 2, 5,15, 0, 3, 2,16, 3, 3, 3,19, 8, 3, 5,32,
00272 14, 3, 2,17, 17, 3, 3, 8, 1, 4, 4,29, 6, 4, 3, 9,
00273 10, 4, 9,45, 2, 5, 9,45, 12, 5, 2,17, 15, 5, 5,16,
00274 1, 6, 3,24, 5, 6, 3, 6, 9, 6, 4,30, 14, 6, 2,16,
00275 17, 6, 4,11, 0, 7, 3, 7, 6, 7, 9,45, 18, 7, 3, 7,
00276 0, 8, 4,11, 5, 8, 2, 4, 8, 8, 4,29, 13, 8, 3,23,
00277 17, 8, 3, 7, 1, 9, 5,16, 7, 9, 2,17, 10, 9, 9,45,
00278 2,10, 9,45, 12,10, 3,23, 16,10, 4,14, 1,11, 3,24,
00279 5,11, 2, 6, 8,11, 5,16, 15,11, 3, 7, 19,11, 2, 8,
00280 0,12, 5,35, 6,12, 4,30, 11,12, 5,15, 17,12, 4,11,
00281 0,13, 2,17, 3,13, 2,16, 6,13, 3,24, 12,13, 3, 6,
00282 18,13, 3, 7, -1
00283 };
00284
00285
00286 const int k8[] = {
00287
00288 22,14,
00289
00290 1, 0, 2, 4, 2, 0, 5,15, 5, 0, 5,16, 6, 0, 2,10,
00291 7, 0, 3,18, 8, 0, 4,29, 10, 0, 5,16, 11, 0, 2, 6,
00292 13, 0, 2, 8, 14, 0, 5,16, 15, 0, 6,38, 18, 0, 5,15,
00293 19, 0, 2, 8, 20, 0, 3, 7, 21, 0, 3, 8, 3, 1, 9,45,
00294 16, 1, 2, 4, 4, 2, 2, 3, 9, 2, 8,39, 17, 2, 2, 3,
00295 1, 3, 2, 5, 6, 3, 6,22, 11, 3, 3,22, 13, 3, 8,38,
00296 19, 3, 9,45, 7, 4, 2, 4, 12, 4, 3,24, 16, 4, 6,38,
00297 20, 4, 3,24, 4, 5, 2,16, 8, 5, 2,14, 17, 5, 2,16,
00298 21, 5, 2,11, 1, 6, 2, 4, 2, 6, 3, 8, 5, 6, 2, 7,
00299 10, 6, 3,18, 14, 6, 2,16, 18, 6, 2,16, 7, 7, 6,22,
00300 11, 7, 3, 7, 15, 7, 2,15, 4, 8, 5,35, 8, 8, 5,34,
00301 12, 8, 5,34, 17, 8, 5,34, 20, 8, 5,34, 21, 8, 2, 3,
00302 5, 9, 2,16, 14, 9, 4,12, 18, 9, 2, 7, 1,10, 3,23,
00303 2,10, 3,21, 6,10, 2, 9, 15,10, 3,20, 3,11, 2,17,
00304 9,11, 2, 4, 11,11, 2, 4, 16,11, 2,10, 21,11, 2,16,
00305 -1,
00306
00307 0, 1, 2, 6, 4, 1, 4,30, 9, 1, 2, 6, 12, 1, 3,10,
00308 17, 1, 4,12, 0, 2, 3, 8, 4, 2, 4,11, 9, 2, 2, 4,
00309 12, 2, 4,20, 17, 2, 4,11, 1, 3, 4,12, 6, 3, 4,28,
00310 13, 3, 5,15, 19, 3, 2, 5, 0, 4, 6,22, 7, 4, 4,28,
00311 12, 4, 3, 8, 16, 4, 3, 6, 0, 5, 3, 7, 4, 5, 3, 7,
00312 8, 5, 8,40, 17, 5, 3,22, 2, 6, 2, 8, 5, 6, 4,12,
00313 10, 6, 3,23, 14, 6, 3,22, 18, 6, 3,22, 0, 7, 6,38,
00314 7, 7, 3,24, 11, 7, 3,23, 15, 7, 6,39, 0, 8, 3, 6,
00315 4, 8, 3, 6, 8, 8, 3, 6, 12, 8, 4,29, 17, 8, 2,14,
00316 1, 9, 3,18, 5, 9, 8,36, 14, 9, 3,22, 18, 9, 3,10,
00317 2,10, 3,22, 6,10, 3,24, 10,10, 4,10, 15,10, 6,21,
00318 0,11, 2,16, 3,11, 5,34, 11,11, 4,29, 16,11, 4,30,
00319 0,12, 4,29, 5,12, 4,12, 10,12, 2,10, 13,12, 4,10,
00320 18,12, 3,23, 0,13, 4,28, 6,13, 3, 7, 10,13, 2,11,
00321 13,13, 4,28, 19,13, 2,13, -1
00322 };
00323
00324
00325 const int k9[] = {
00326
00327 22,14,
00328
00329 1, 0, 4,10, 2, 0, 4,24, 3, 0, 3, 7, 7, 0, 3, 8,
00330 8, 0, 2,17, 9, 0, 3,13, 13, 0, 3,22, 14, 0, 2,12,
00331 15, 0, 3,24, 19, 0, 3,19, 20, 0, 4,28, 21, 0, 4,14,
00332 4, 1, 5,16, 6, 1, 5,17, 10, 1, 5,32, 12, 1, 5,34,
00333 16, 1, 5,35, 18, 1, 5,31, 5, 2, 3, 9, 11, 2, 3, 7,
00334 17, 2, 3, 7, 3, 4, 5,27, 7, 4, 5,16, 9, 4, 5,20,
00335 13, 4, 5,30, 15, 4, 5,30, 19, 4, 5,26, 1, 5, 3,12,
00336 2, 5, 3,20, 8, 5, 3,22, 14, 5, 3, 9, 20, 5, 3,10,
00337 21, 5, 3,20, 4, 7, 5,31, 6, 7, 5,16, 10, 7, 5,17,
00338 12, 7, 5,32, 16, 7, 5,19, 18, 7, 5,34, 5, 8, 3, 8,
00339 11, 8, 3,24, 17, 8, 3,24, 1, 9, 4,10, 2, 9, 4,15,
00340 20, 9, 4,30, 21, 9, 4,12, 3,10, 3,20, 7,10, 3, 6,
00341 9,10, 3, 9, 13,10, 3, 6, 15,10, 3, 7, 19,10, 3,24,
00342 8,11, 2, 8, 14,11, 2, 7, -1,
00343
00344 0, 1, 3, 7, 6, 1, 3,12, 12, 1, 3,23, 18, 1, 3,23,
00345 0, 2, 4,11, 5, 2, 5,19, 11, 2, 5,33, 17, 2, 4,28,
00346 0, 3, 7,28, 8, 3, 5,34, 14, 3, 7,29, 0, 4, 2,12,
00347 3, 4, 3, 7, 9, 4, 3,16, 15, 4, 3,10, 19, 4, 2,10,
00348 2, 5, 5,18, 8, 5, 5,20, 14, 5, 5,29, 0, 6, 4,24,
00349 5, 6, 5,35, 11, 6, 5,23, 17, 6, 4,26, 0, 7, 3,23,
00350 6, 7, 3, 9, 12, 7, 3,10, 18, 7, 3,23, 0, 8, 4,15,
00351 5, 8, 5,19, 11, 8, 5,33, 17, 8, 4,10, 2, 9, 5,19,
00352 8, 9, 5,35, 14, 9, 5,31, 0,10, 2, 4, 3,10, 3,10,
00353 9,10, 3,18, 15,10, 3,24, 19,10, 2,12, 0,11, 7,41,
00354 8,11, 5,23, 14,11, 7,36, 0,12, 4,14, 5,12, 5,17,
00355 11,12, 5,15, 17,12, 4,26, 0,13, 3, 7, 6,13, 3, 7,
00356 12,13, 3, 6, 18,13, 3,23, -1
00357 };
00359
00361 const int* examples[] = {
00362 &k0[0], &k1[0], &k2[0], &k3[0], &k4[0],
00363 &k5[0], &k6[0], &k7[0], &k8[0], &k9[0]
00364 };
00366 const unsigned int n_examples = sizeof(examples)/sizeof(const int*);
00367
00368
00372 class DistinctLinear : public Space {
00373 protected:
00375 IntVarArray x;
00376 public:
00378 DistinctLinear(int n, int s) : x(*this,n,1,9) {
00379 distinct(*this, x);
00380 linear(*this, x, IRT_EQ, s);
00381 branch(*this, x, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
00382 }
00384 DistinctLinear(DistinctLinear& s) : Space(s) {
00385 x.update(*this, s.x);
00386 }
00388 virtual Space*
00389 copy(void) {
00390 return new DistinctLinear(*this);
00391 }
00393 IntArgs solution(void) const {
00394 IntArgs s(x.size());
00395 for (int i=0; i<x.size(); i++)
00396 s[i]=x[i].val();
00397 return s;
00398 }
00399 };
00400
00404 TupleSet generate(int n, int c) {
00405
00406 DistinctLinear* e = new DistinctLinear(n,c);
00407 DFS<DistinctLinear> d(e);
00408 delete e;
00409 TupleSet ts(n);
00410 while (DistinctLinear* s = d.next()) {
00411 ts.add(s->solution()); delete s;
00412 }
00413 ts.finalize();
00414 return ts;
00415 }
00416
00420 class Cache {
00421 private:
00423 class Entry {
00424 public:
00425 int n;
00426 int c;
00427 TupleSet ts;
00428 Entry* next;
00429 };
00430 Entry* cache;
00431 public:
00433 Cache(void) : cache(NULL) {}
00435 TupleSet get(int n, int c) {
00436 for (Entry* e = cache; e != NULL; e = e->next)
00437 if ((e->n == n) && (e->c == c))
00438 return e->ts;
00439 {
00440 Entry* e = new Entry;
00441 e->n = n;
00442 e->c = c;
00443 e->ts = generate(n,c);
00444 e->next = cache;
00445 cache = e;
00446 }
00447 return cache->ts;
00448 }
00450 ~Cache(void) {
00451 Entry* e = cache;
00452 while (e != NULL) {
00453 Entry* d = e;
00454 e = e->next;
00455 delete d;
00456 }
00457 }
00458 };
00459
00460 }
00461
00462
00473 class Kakuro : public Script {
00474 protected:
00475 const int w;
00476 const int h;
00477 IntVarArray f;
00478 public:
00480 enum {
00481 MODEL_DECOMPOSE,
00482 MODEL_COMBINE,
00483 };
00485 IntVar init(IntVar& x) {
00486 if (x.min() == 0)
00487 x = IntVar(*this,1,9);
00488 return x;
00489 }
00491 void distinctlinear(Cache& dc, const IntVarArgs& x, int c,
00492 const SizeOptions& opt) {
00493 int n=x.size();
00494 if (opt.model() == MODEL_DECOMPOSE) {
00495 if (n < 8)
00496 linear(*this, x, IRT_EQ, c, opt.ipl());
00497 else if (n == 8)
00498 rel(*this, x, IRT_NQ, 9*(9+1)/2 - c);
00499 distinct(*this, x, opt.ipl());
00500 } else {
00501 switch (n) {
00502 case 0:
00503 return;
00504 case 1:
00505 rel(*this, x[0], IRT_EQ, c);
00506 return;
00507 case 8:
00508
00509 rel(*this, x, IRT_NQ, 9*(9+1)/2 - c);
00510 break;
00511 case 9:
00512 break;
00513 default:
00514 if (c == n*(n+1)/2) {
00515
00516 rel(*this, x, IRT_LQ, n);
00517 } else if (c == n*(n+1)/2 + 1) {
00518
00519 rel(*this, x, IRT_LQ, n+1);
00520 rel(*this, x, IRT_NQ, n);
00521 } else if (c == 9*(9+1)/2 - (9-n)*(9-n+1)/2) {
00522
00523 rel(*this, x, IRT_GQ, 9-n+1);
00524 } else if (c == 9*(9+1)/2 - (9-n)*(9-n+1)/2 + 1) {
00525
00526 rel(*this, x, IRT_GQ, 9-n);
00527 rel(*this, x, IRT_NQ, 9-n+1);
00528 } else {
00529 extensional(*this, x, dc.get(n,c));
00530 return;
00531 }
00532 }
00533 distinct(*this, x, opt.ipl());
00534 }
00535 }
00537 Kakuro(const SizeOptions& opt)
00538 : Script(opt),
00539 w(examples[opt.size()][0]), h(examples[opt.size()][1]),
00540 f(*this,w*h) {
00541 IntVar black(*this,0,0);
00542
00543
00544
00545 for (int i=w*h; i--; )
00546 f[i] = black;
00547
00548
00549 Cache cache;
00550
00551
00552 Matrix<IntVarArray> b(f,w,h);
00553
00554 const int* k = &examples[opt.size()][2];
00555
00556
00557 while (*k >= 0) {
00558 int x=*k++; int y=*k++; int n=*k++; int s=*k++;
00559 IntVarArgs col(n);
00560 for (int i=n; i--; )
00561 col[i]=init(b(x,y+i+1));
00562 distinctlinear(cache,col,s,opt);
00563 }
00564 k++;
00565
00566
00567 while (*k >= 0) {
00568 int x=*k++; int y=*k++; int n=*k++; int s=*k++;
00569 IntVarArgs row(n);
00570 for (int i=n; i--; )
00571 row[i]=init(b(x+i+1,y));
00572 distinctlinear(cache,row,s,opt);
00573 }
00574 branch(*this, f, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_SPLIT_MIN());
00575 }
00577 Kakuro(Kakuro& s) : Script(s), w(s.w), h(s.h) {
00578 f.update(*this, s.f);
00579 }
00581 virtual Space*
00582 copy(void) {
00583 return new Kakuro(*this);
00584 }
00586 virtual void
00587 print(std::ostream& os) const {
00588 Matrix<IntVarArray> b(f,w,h);
00589 for (int y=0; y<h; y++) {
00590 os << '\t';
00591 for (int x=0; x<w; x++)
00592 if (b(x,y).min() == 0)
00593 os << ". ";
00594 else
00595 os << b(x,y) << ' ';
00596 os << std::endl;
00597 }
00598 }
00599 };
00600
00601
00605 int
00606 main(int argc, char* argv[]) {
00607 SizeOptions opt("Kakuro");
00608 opt.model(Kakuro::MODEL_COMBINE);
00609 opt.model(Kakuro::MODEL_DECOMPOSE,
00610 "decompose","decompose distinct and linear constraints");
00611 opt.model(Kakuro::MODEL_COMBINE,
00612 "combine","combine distinct and linear constraints");
00613 opt.ipl(IPL_DOM);
00614 opt.parse(argc,argv);
00615 if (opt.size() >= n_examples) {
00616 std::cerr << "Error: size must be between 0 and "
00617 << n_examples-1 << std::endl;
00618 return 1;
00619 }
00620 Script::run<Kakuro,DFS,SizeOptions>(opt);
00621 return 0;
00622 }
00623
00624