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
00039
00040
00041
00042 #include <gecode/driver.hh>
00043 #include <gecode/int.hh>
00044 #include <gecode/minimodel.hh>
00045
00046 using namespace Gecode;
00047
00048 namespace {
00049
00070
00071
00072 const int k0[] = {
00073
00074 12,10,
00075
00076 2, 0, 5,16, 3, 0, 2, 4, 5, 0, 3, 6, 6, 0, 2, 4,
00077 7, 0, 5,15, 10, 0, 3, 6, 11, 0, 3, 7, 1, 1, 3, 7,
00078 9, 1, 5,16, 4, 2, 2, 5, 8, 2, 2, 3, 3, 3, 5,16,
00079 6, 3, 3, 8, 5, 4, 5,15, 10, 4, 5,15, 4, 5, 2, 3,
00080 8, 5, 2, 4, 11, 5, 3, 7, 1, 6, 3, 6, 2, 6, 3, 7,
00081 7, 6, 3, 7, 6, 7, 2, 3, 9, 7, 2, 4, -1,
00082
00083 1, 1, 2, 7, 4, 1, 3, 9, 9, 1, 2, 4, 0, 2, 3, 7,
00084 4, 2, 3, 7, 8, 2, 3, 6, 0, 3, 2, 3, 3, 3, 2, 4,
00085 6, 3, 5,16, 0, 4, 4,10, 5, 4, 4,10, 1, 5, 2,10,
00086 4, 5, 3, 6, 8, 5, 2, 5, 2, 6, 4,10, 7, 6, 4,12,
00087 0, 7, 5,16, 6, 7, 2, 4, 9, 7, 2, 4, 0, 8, 3, 7,
00088 4, 8, 3, 8, 8, 8, 3, 6, 0, 9, 2, 3, 4, 9, 3, 7,
00089 8, 9, 2, 3, -1
00090 };
00091
00092
00093 const int k1[] = {
00094
00095 12,10,
00096
00097 1, 0, 2, 4, 2, 0, 5,15, 5, 0, 5,18, 6, 0, 2,12,
00098 7, 0, 3, 8, 10, 0, 3,24, 11, 0, 3,23, 3, 1, 2, 7,
00099 9, 1, 3,24, 4, 2, 5,16, 8, 2, 5,35, 1, 3, 2,12,
00100 6, 3, 3,17, 7, 4, 5,34, 10, 4, 5,34, 11, 4, 2,16,
00101 3, 5, 3, 6, 1, 6, 3, 7, 2, 6, 3, 6, 5, 6, 3,23,
00102 9, 6, 2,10, 6, 7, 2,14, 11, 7, 2,10, -1,
00103
00104 0, 1, 2, 3, 4, 1, 3,15, 9, 1, 2,16, 0, 2, 3, 6,
00105 4, 2, 3, 7, 8, 2, 3,24, 1, 3, 4,11, 6, 3, 5,34,
00106 0, 4, 2,14, 3, 4, 3,23, 7, 4, 2,14, 0, 5, 2, 7,
00107 3, 5, 5,15, 9, 5, 2,17, 2, 6, 2, 6, 5, 6, 3,23,
00108 9, 6, 2,13, 0, 7, 5,16, 6, 7, 4,30, 0, 8, 3, 6,
00109 4, 8, 3,23, 8, 8, 3, 7, 0, 9, 2, 4, 4, 9, 3,24,
00110 9, 9, 2,17, -1
00111 };
00112
00113
00114 const int k2[] = {
00115
00116 12,10,
00117
00118 2, 0, 5,15, 3, 0, 2, 3, 7, 0, 3, 7, 8, 0, 4,23,
00119 9, 0, 2,12, 10, 0, 3,20, 11, 0, 3, 9, 4, 1, 3, 7,
00120 5, 1, 4,10, 1, 2, 3, 6, 6, 2, 5,15, 9, 3, 2,16,
00121 3, 4, 2, 3, 7, 4, 4,13, 10, 4, 5,35, 11, 4, 3,23,
00122 4, 5, 4,11, 8, 5, 3,23, 1, 6, 3,23, 2, 6, 3,14,
00123 5, 6, 3,11, 3, 7, 2,13, 9, 7, 2,17, -1,
00124
00125 1, 1, 2, 4, 6, 1, 5,15, 1, 2, 4,11, 6, 2, 5,34,
00126 0, 3, 2, 3, 3, 3, 5,15, 9, 3, 2,10, 0, 4, 2, 4,
00127 3, 4, 3, 6, 7, 4, 2,17, 0, 5, 3, 7, 4, 5, 3, 8,
00128 8, 5, 3,18, 2, 6, 2, 3, 5, 6, 3,11, 9, 6, 2,16,
00129 0, 7, 2,16, 3, 7, 5,16, 9, 7, 2,17, 0, 8, 5,16,
00130 6, 8, 4,30, 0, 9, 5,35, 8, 9, 2,17, -1
00131 };
00132
00133
00134 const int k3[] = {
00135
00136 12,10,
00137
00138 3, 0, 3, 7, 4, 0, 6,21, 7, 0, 4,29, 8, 0, 2,17,
00139 10, 0, 4,29, 11, 0, 3,23, 2, 1, 3, 6, 6, 1, 2,16,
00140 9, 1, 4,14, 1, 2, 2, 4, 5, 2, 2, 3, 8, 3, 6,22,
00141 3, 4, 4,10, 2, 5, 4,11, 5, 5, 4,10, 7, 5, 2,10,
00142 10, 5, 3,24, 11, 5, 2,16, 1, 6, 3, 7, 6, 6, 2, 9,
00143 9, 6, 3,23, 4, 7, 2, 4, -1,
00144
00145 2, 1, 2, 4, 6, 1, 2,17, 9, 1, 2,16, 1, 2, 3, 6,
00146 5, 2, 6,39, 0, 3, 7,28, 8, 3, 3,24, 0, 4, 2, 3,
00147 3, 4, 2, 3, 6, 4, 4,20, 2, 5, 2, 9, 7, 5, 2, 4,
00148 1, 6, 4,10, 6, 6, 2, 3, 9, 6, 2,16, 0, 7, 3, 6,
00149 4, 7, 7,42, 0, 8, 6,21, 7, 8, 3,21, 0, 9, 2, 4,
00150 3, 9, 2, 3, 7, 9, 2,16, -1
00151 };
00152
00153
00154 const int k4[] = {
00155
00156 20,12,
00157
00158 3, 0, 3,21, 4, 0, 2, 4, 5, 0, 4,11, 8, 0, 2, 8,
00159 9, 0, 3, 7, 11, 0, 2, 3, 12, 0, 3, 6, 15, 0, 6,39,
00160 16, 0, 2, 3, 17, 0, 3,23, 2, 1, 5,15, 6, 1, 4,10,
00161 10, 1, 4,11, 14, 1, 4,11, 18, 1, 3, 6, 1, 2, 3,24,
00162 7, 2, 4,14, 13, 2, 2,10, 19, 2, 2,16, 4, 3, 5,18,
00163 8, 3, 4,10, 11, 3, 4,12, 16, 3, 5,33, 3, 4, 3,23,
00164 9, 4, 4,29, 12, 4, 4,30, 17, 4, 3,18, 5, 5, 6,38,
00165 13, 5, 4,29, 18, 5, 5,15, 6, 6, 4,25, 10, 6, 4,12,
00166 14, 6, 4,28, 19, 6, 3,21, 1, 7, 2, 4, 2, 7, 3, 7,
00167 7, 7, 2, 7, 15, 7, 4,11, 3, 8, 3,19, 8, 8, 3,24,
00168 11, 8, 3, 7, 17, 8, 3, 6, 4, 9, 2,16, 9, 9, 2,16,
00169 12, 9, 2,17, 16, 9, 2, 5, -1,
00170
00171 2, 1, 3, 7, 7, 1, 2, 4, 10, 1, 2, 4, 14, 1, 3,19,
00172 1, 2, 5,18, 7, 2, 5,15, 13, 2, 5,16, 0, 3, 3,21,
00173 4, 3, 3, 6, 8, 3, 2, 3, 11, 3, 4,11, 16, 3, 3,20,
00174 0, 4, 2,14, 3, 4, 5,15, 9, 4, 2, 3, 12, 4, 4,29,
00175 17, 4, 2, 8, 0, 5, 4,27, 5, 5, 7,42, 13, 5, 4,12,
00176 1, 6, 4,12, 6, 6, 3, 8, 10, 6, 3,20, 14, 6, 4,29,
00177 2, 7, 4,28, 7, 7, 7,28, 15, 7, 4,28, 0, 8, 2, 3,
00178 3, 8, 4,11, 8, 8, 2,10, 11, 8, 5,35, 17, 8, 2,10,
00179 0, 9, 3, 6, 4, 9, 4,30, 9, 9, 2, 3, 12, 9, 3,19,
00180 16, 9, 3, 7, 1,10, 5,34, 7,10, 5,34, 13,10, 5,17,
00181 2,11, 3,23, 7,11, 2,17, 10,11, 2,10, 14,11, 3, 6,
00182 -1
00183 };
00184
00185
00186 const int k5[] = {
00187
00188 20,12,
00189
00190 1, 0, 2, 3, 2, 0, 5,33, 4, 0, 2, 8, 5, 0, 4,14,
00191 7, 0, 5,15, 8, 0, 3,19, 9, 0, 2,12, 11, 0, 4,11,
00192 12, 0, 2, 4, 13, 0, 5,16, 15, 0, 4,11, 16, 0, 2,17,
00193 18, 0, 5,34, 19, 0, 2,17, 3, 1, 2, 3, 10, 1, 9,45,
00194 17, 1, 2,16, 6, 2, 3,20, 14, 2, 3,12, 1, 3, 2,13,
00195 4, 3, 5,33, 9, 3, 3,20, 16, 3, 5,21, 19, 3, 2, 8,
00196 3, 4, 3,11, 8, 4, 3,11, 12, 4, 3, 7, 17, 4, 3, 8,
00197 11, 5, 3,23, 1, 6, 2,11, 2, 6, 5,15, 6, 6, 3,23,
00198 7, 6, 5,27, 13, 6, 5,30, 14, 6, 3, 7, 18, 6, 5,15,
00199 19, 6, 2, 3, 5, 7, 4,26, 9, 7, 4,27, 15, 7, 4,27,
00200 3, 8, 2, 7, 12, 8, 3,24, 17, 8, 2,17, 1, 9, 2, 5,
00201 4, 9, 2, 9, 8, 9, 2, 3, 11, 9, 2,16, 16, 9, 2,16,
00202 19, 9, 2,10, -1,
00203
00204 0, 1, 2, 4, 3, 1, 2, 7, 6, 1, 3, 7, 10, 1, 3, 7,
00205 14, 1, 2,11, 17, 1, 2,16, 0, 2, 5,16, 6, 2, 7,42,
00206 14, 2, 5,35, 1, 3, 2,10, 4, 3, 4,15, 9, 3, 2, 6,
00207 12, 3, 3, 7, 16, 3, 2,13, 0, 4, 2,17, 3, 4, 4,29,
00208 8, 4, 3,19, 12, 4, 4,11, 17, 4, 2, 9, 0, 5, 4,29,
00209 5, 5, 5,33, 11, 5, 3, 6, 15, 5, 4,29, 2, 6, 2, 4,
00210 7, 6, 5,16, 15, 6, 2, 4, 0, 7, 4,12, 5, 7, 3,10,
00211 9, 7, 5,18, 15, 7, 4,12, 0, 8, 2,13, 3, 8, 4,29,
00212 8, 8, 3,24, 12, 8, 4,23, 17, 8, 2, 5, 1, 9, 2, 6,
00213 4, 9, 3,24, 8, 9, 2, 4, 11, 9, 4,28, 16, 9, 2,11,
00214 0,10, 5,15, 6,10, 7,41, 14,10, 5,34, 0,11, 2, 3,
00215 3,11, 2,17, 6,11, 3,14, 10,11, 3,23, 14,11, 2,11,
00216 17,11, 2, 4, -1
00217 };
00218
00219
00220 const int k6[] = {
00221
00222 20,12,
00223
00224 1, 0, 2, 6, 2, 0, 2,16, 4, 0, 3,10, 5, 0, 2,12,
00225 9, 0, 7,28, 10, 0, 2,12, 11, 0, 3,24, 15, 0, 3,10,
00226 16, 0, 2,17, 17, 0, 6,22, 3, 1, 3,18, 6, 1, 4,10,
00227 8, 1, 2, 8, 12, 1, 2,10, 13, 1, 3,18, 18, 1, 3,12,
00228 7, 2, 4,11, 14, 2, 3, 7, 19, 2, 2, 7, 1, 3, 2, 8,
00229 2, 3, 3, 7, 5, 3, 4,25, 10, 3, 2, 4, 16, 3, 4,15,
00230 4, 4, 4,11, 11, 4, 7,42, 12, 4, 2,17, 15, 4, 4,26,
00231 3, 5, 6,22, 8, 5, 2,16, 13, 5, 4,30, 18, 5, 3,24,
00232 6, 6, 3, 7, 10, 6, 2, 4, 14, 6, 4,29, 19, 6, 2,14,
00233 1, 7, 2,16, 2, 7, 3,11, 7, 7, 3,24, 17, 7, 3,21,
00234 5, 8, 3,23, 8, 8, 2,12, 9, 8, 3,20, 12, 8, 2,17,
00235 16, 8, 3, 6, 4, 9, 2, 9, 10, 9, 2,16, 15, 9, 2, 9,
00236 18, 9, 2, 3, 19, 9, 2,12, -1,
00237
00238 0, 1, 2,10, 3, 1, 2, 5, 8, 1, 3,23, 14, 1, 3,11,
00239 0, 2, 6,38, 7, 2, 6,39, 14, 2, 4,30, 2, 3, 2,10,
00240 5, 3, 4,11, 10, 3, 5,18, 16, 3, 3, 7, 0, 4, 3, 7,
00241 4, 4, 3, 7, 8, 4, 2, 6, 12, 4, 2, 8, 15, 4, 4,11,
00242 0, 5, 2, 8, 3, 5, 4,14, 8, 5, 4,24, 13, 5, 4,10,
00243 1, 6, 4,13, 6, 6, 3,14, 10, 6, 3,19, 14, 6, 4,29,
00244 2, 7, 4,15, 7, 7, 4,14, 12, 7, 4,29, 17, 7, 2,16,
00245 0, 8, 4,29, 5, 8, 2,13, 9, 8, 2, 8, 12, 8, 3,23,
00246 16, 8, 3,22, 0, 9, 3,10, 4, 9, 5,32, 10, 9, 4,29,
00247 15, 9, 2,10, 1,10, 4,14, 6,10, 6,39, 13,10, 6,22,
00248 2,11, 3,21, 8,11, 3,23, 14,11, 2, 6, 17,11, 2,11,
00249 -1
00250 };
00251
00252
00253 const int k7[] = {
00254
00255 22,14,
00256
00257 1, 0, 3,23, 2, 0, 4,29, 3, 0, 2,16, 7, 0, 2, 7,
00258 8, 0, 2,10, 9, 0, 5,30, 13, 0, 7,41, 14, 0, 2,16,
00259 15, 0, 4,29, 17, 0, 2, 3, 18, 0, 6,21, 20, 0, 3, 7,
00260 21, 0, 2, 4, 4, 1, 5,35, 6, 1, 2, 4, 10, 1, 2,17,
00261 12, 1, 3,24, 19, 1, 9,45, 5, 2, 3,23, 11, 2, 9,45,
00262 16, 2, 4,21, 3, 3, 9,45, 7, 3, 5,15, 8, 3, 4,10,
00263 14, 3, 2,10, 17, 3, 2, 3, 6, 4, 2, 4, 10, 4, 4,30,
00264 20, 4, 4,11, 2, 5, 4,13, 12, 5, 4,30, 15, 5, 5,35,
00265 21, 5, 2, 4, 1, 6, 2, 4, 9, 6, 7,41, 14, 6, 4,29,
00266 4, 7, 6,38, 6, 7, 4,11, 16, 7, 2,16, 18, 7, 5,15,
00267 5, 8, 2, 9, 8, 8, 2,17, 13, 8, 5,16, 17, 8, 3, 7,
00268 7, 9, 4,20, 10, 9, 3,23, 20, 9, 4,12, 2,10, 3,23,
00269 12,10, 2, 6, 16,10, 2, 4, 21,10, 3, 9, 1,11, 2,16,
00270 5,11, 2,16, 8,11, 2,16, 14,11, 2, 6, 15,11, 2, 4,
00271 19,11, 2, 4, -1,
00272
00273 0, 1, 3,23, 6, 1, 3, 8, 12, 1, 3,23, 16, 1, 2, 4,
00274 19, 1, 2, 4, 0, 2, 4,30, 5, 2, 5,31, 11, 2, 4,29,
00275 16, 2, 5,15, 0, 3, 2,16, 3, 3, 3,19, 8, 3, 5,32,
00276 14, 3, 2,17, 17, 3, 3, 8, 1, 4, 4,29, 6, 4, 3, 9,
00277 10, 4, 9,45, 2, 5, 9,45, 12, 5, 2,17, 15, 5, 5,16,
00278 1, 6, 3,24, 5, 6, 3, 6, 9, 6, 4,30, 14, 6, 2,16,
00279 17, 6, 4,11, 0, 7, 3, 7, 6, 7, 9,45, 18, 7, 3, 7,
00280 0, 8, 4,11, 5, 8, 2, 4, 8, 8, 4,29, 13, 8, 3,23,
00281 17, 8, 3, 7, 1, 9, 5,16, 7, 9, 2,17, 10, 9, 9,45,
00282 2,10, 9,45, 12,10, 3,23, 16,10, 4,14, 1,11, 3,24,
00283 5,11, 2, 6, 8,11, 5,16, 15,11, 3, 7, 19,11, 2, 8,
00284 0,12, 5,35, 6,12, 4,30, 11,12, 5,15, 17,12, 4,11,
00285 0,13, 2,17, 3,13, 2,16, 6,13, 3,24, 12,13, 3, 6,
00286 18,13, 3, 7, -1
00287 };
00288
00289
00290 const int k8[] = {
00291
00292 22,14,
00293
00294 1, 0, 2, 4, 2, 0, 5,15, 5, 0, 5,16, 6, 0, 2,10,
00295 7, 0, 3,18, 8, 0, 4,29, 10, 0, 5,16, 11, 0, 2, 6,
00296 13, 0, 2, 8, 14, 0, 5,16, 15, 0, 6,38, 18, 0, 5,15,
00297 19, 0, 2, 8, 20, 0, 3, 7, 21, 0, 3, 8, 3, 1, 9,45,
00298 16, 1, 2, 4, 4, 2, 2, 3, 9, 2, 8,39, 17, 2, 2, 3,
00299 1, 3, 2, 5, 6, 3, 6,22, 11, 3, 3,22, 13, 3, 8,38,
00300 19, 3, 9,45, 7, 4, 2, 4, 12, 4, 3,24, 16, 4, 6,38,
00301 20, 4, 3,24, 4, 5, 2,16, 8, 5, 2,14, 17, 5, 2,16,
00302 21, 5, 2,11, 1, 6, 2, 4, 2, 6, 3, 8, 5, 6, 2, 7,
00303 10, 6, 3,18, 14, 6, 2,16, 18, 6, 2,16, 7, 7, 6,22,
00304 11, 7, 3, 7, 15, 7, 2,15, 4, 8, 5,35, 8, 8, 5,34,
00305 12, 8, 5,34, 17, 8, 5,34, 20, 8, 5,34, 21, 8, 2, 3,
00306 5, 9, 2,16, 14, 9, 4,12, 18, 9, 2, 7, 1,10, 3,23,
00307 2,10, 3,21, 6,10, 2, 9, 15,10, 3,20, 3,11, 2,17,
00308 9,11, 2, 4, 11,11, 2, 4, 16,11, 2,10, 21,11, 2,16,
00309 -1,
00310
00311 0, 1, 2, 6, 4, 1, 4,30, 9, 1, 2, 6, 12, 1, 3,10,
00312 17, 1, 4,12, 0, 2, 3, 8, 4, 2, 4,11, 9, 2, 2, 4,
00313 12, 2, 4,20, 17, 2, 4,11, 1, 3, 4,12, 6, 3, 4,28,
00314 13, 3, 5,15, 19, 3, 2, 5, 0, 4, 6,22, 7, 4, 4,28,
00315 12, 4, 3, 8, 16, 4, 3, 6, 0, 5, 3, 7, 4, 5, 3, 7,
00316 8, 5, 8,40, 17, 5, 3,22, 2, 6, 2, 8, 5, 6, 4,12,
00317 10, 6, 3,23, 14, 6, 3,22, 18, 6, 3,22, 0, 7, 6,38,
00318 7, 7, 3,24, 11, 7, 3,23, 15, 7, 6,39, 0, 8, 3, 6,
00319 4, 8, 3, 6, 8, 8, 3, 6, 12, 8, 4,29, 17, 8, 2,14,
00320 1, 9, 3,18, 5, 9, 8,36, 14, 9, 3,22, 18, 9, 3,10,
00321 2,10, 3,22, 6,10, 3,24, 10,10, 4,10, 15,10, 6,21,
00322 0,11, 2,16, 3,11, 5,34, 11,11, 4,29, 16,11, 4,30,
00323 0,12, 4,29, 5,12, 4,12, 10,12, 2,10, 13,12, 4,10,
00324 18,12, 3,23, 0,13, 4,28, 6,13, 3, 7, 10,13, 2,11,
00325 13,13, 4,28, 19,13, 2,13, -1
00326 };
00327
00328
00329 const int k9[] = {
00330
00331 22,14,
00332
00333 1, 0, 4,10, 2, 0, 4,24, 3, 0, 3, 7, 7, 0, 3, 8,
00334 8, 0, 2,17, 9, 0, 3,13, 13, 0, 3,22, 14, 0, 2,12,
00335 15, 0, 3,24, 19, 0, 3,19, 20, 0, 4,28, 21, 0, 4,14,
00336 4, 1, 5,16, 6, 1, 5,17, 10, 1, 5,32, 12, 1, 5,34,
00337 16, 1, 5,35, 18, 1, 5,31, 5, 2, 3, 9, 11, 2, 3, 7,
00338 17, 2, 3, 7, 3, 4, 5,27, 7, 4, 5,16, 9, 4, 5,20,
00339 13, 4, 5,30, 15, 4, 5,30, 19, 4, 5,26, 1, 5, 3,12,
00340 2, 5, 3,20, 8, 5, 3,22, 14, 5, 3, 9, 20, 5, 3,10,
00341 21, 5, 3,20, 4, 7, 5,31, 6, 7, 5,16, 10, 7, 5,17,
00342 12, 7, 5,32, 16, 7, 5,19, 18, 7, 5,34, 5, 8, 3, 8,
00343 11, 8, 3,24, 17, 8, 3,24, 1, 9, 4,10, 2, 9, 4,15,
00344 20, 9, 4,30, 21, 9, 4,12, 3,10, 3,20, 7,10, 3, 6,
00345 9,10, 3, 9, 13,10, 3, 6, 15,10, 3, 7, 19,10, 3,24,
00346 8,11, 2, 8, 14,11, 2, 7, -1,
00347
00348 0, 1, 3, 7, 6, 1, 3,12, 12, 1, 3,23, 18, 1, 3,23,
00349 0, 2, 4,11, 5, 2, 5,19, 11, 2, 5,33, 17, 2, 4,28,
00350 0, 3, 7,28, 8, 3, 5,34, 14, 3, 7,29, 0, 4, 2,12,
00351 3, 4, 3, 7, 9, 4, 3,16, 15, 4, 3,10, 19, 4, 2,10,
00352 2, 5, 5,18, 8, 5, 5,20, 14, 5, 5,29, 0, 6, 4,24,
00353 5, 6, 5,35, 11, 6, 5,23, 17, 6, 4,26, 0, 7, 3,23,
00354 6, 7, 3, 9, 12, 7, 3,10, 18, 7, 3,23, 0, 8, 4,15,
00355 5, 8, 5,19, 11, 8, 5,33, 17, 8, 4,10, 2, 9, 5,19,
00356 8, 9, 5,35, 14, 9, 5,31, 0,10, 2, 4, 3,10, 3,10,
00357 9,10, 3,18, 15,10, 3,24, 19,10, 2,12, 0,11, 7,41,
00358 8,11, 5,23, 14,11, 7,36, 0,12, 4,14, 5,12, 5,17,
00359 11,12, 5,15, 17,12, 4,26, 0,13, 3, 7, 6,13, 3, 7,
00360 12,13, 3, 6, 18,13, 3,23, -1
00361 };
00363
00365 const int* examples[] = {
00366 &k0[0], &k1[0], &k2[0], &k3[0], &k4[0],
00367 &k5[0], &k6[0], &k7[0], &k8[0], &k9[0]
00368 };
00370 const unsigned int n_examples = sizeof(examples)/sizeof(const int*);
00371
00372
00376 class DistinctLinear : public Space {
00377 public:
00379 IntVarArray x;
00381 DistinctLinear(int n, int s) : x(*this,n,1,9) {
00382 distinct(*this, x);
00383 linear(*this, x, IRT_EQ, s);
00384 branch(*this, x, INT_VAR_NONE, INT_VAL_SPLIT_MIN);
00385 }
00387 DistinctLinear(bool share, DistinctLinear& s) : Space(share,s) {
00388 x.update(*this, share, s.x);
00389 }
00391 virtual Space*
00392 copy(bool share) {
00393 return new DistinctLinear(share,*this);
00394 }
00395 };
00402 template<class C> C generate(int n, int c);
00403
00407 template<>
00408 DFA generate<DFA>(int n, int c) {
00409
00410 DistinctLinear* e = new DistinctLinear(n,c);
00411 DFS<DistinctLinear> d(e);
00412 delete e;
00413
00414 DFA::Transition* ts = new DFA::Transition[n];
00415 for (int i=n; i--; )
00416 ts[i].symbol = 0;
00417 ts[0].i_state = 0;
00418
00419 Support::DynamicArray<DFA::Transition,Heap> ts_all(heap);
00420 int ts_next = 0;
00421 int n_state = 2;
00422 while (DistinctLinear* s = d.next()) {
00423 int i=0;
00424
00425 for (; ts[i].symbol == s->x[i].val(); i++) {}
00426
00427 int i_state = ts[i].i_state;
00428 for (;i<n;i++) {
00429 ts[i].i_state = i_state;
00430 ts[i].symbol = s->x[i].val();
00431 ts[i].o_state = i_state = n_state++;
00432 ts_all[ts_next++] = ts[i];
00433 }
00434
00435 ts_all[ts_next-1].o_state = 1;
00436 delete s;
00437 }
00438 delete [] ts;
00439 ts_all[ts_next].i_state = -1;
00440 int final[2] = {1,-1};
00441 DFA dfa(0,&ts_all[0],final);
00442 return dfa;
00443 }
00447 template<>
00448 TupleSet generate<TupleSet>(int n, int c) {
00449
00450 DistinctLinear* e = new DistinctLinear(n,c);
00451 DFS<DistinctLinear> d(e);
00452 delete e;
00453 TupleSet ts;
00454 while (DistinctLinear* s = d.next()) {
00455 IntArgs ia(n);
00456 for (int i = n; i--; ) ia[i] = s->x[i].val();
00457 ts.add(ia);
00458 delete s;
00459 }
00460 ts.finalize();
00461 return ts;
00462 }
00463
00467 template<class Data>
00468 class Cache {
00469 private:
00470 class Entry {
00471 public:
00472 int n;
00473 int c;
00474 Data d;
00475 Entry* next;
00476 };
00477 Entry* cache;
00478 public:
00480 Cache(void) : cache(NULL) {}
00482 Data get(int n, int c) {
00483 for (Entry* e = cache; e != NULL; e = e->next)
00484 if ((e->n == n) && (e->c == c))
00485 return e->d;
00486 Entry* e = new Entry;
00487 e->n = n;
00488 e->c = c;
00489 e->d = generate<Data>(n,c);
00490 e->next = cache;
00491 cache = e;
00492 return cache->d;
00493 }
00495 ~Cache(void) {
00496 Entry* e = cache;
00497 while (e != NULL) {
00498 Entry* d = e;
00499 e = e->next;
00500 delete d;
00501 }
00502 }
00503 };
00504
00505 }
00506
00507
00515 class Kakuro : public Script {
00516 protected:
00517 const int w;
00518 const int h;
00519 IntVarArray _b;
00520 public:
00522 enum {
00523 PROP_DFA,
00524 PROP_TUPLE_SET
00525 };
00527 enum {
00528 MODEL_DECOMPOSE,
00529 MODEL_COMBINE,
00530 };
00532 IntVar& b(int x, int y) {
00533 assert((x >= 0) && (x < w) && (y >= 0) && (y < h));
00534 return _b[x+y*w];
00535 }
00537 const IntVar& b(int x, int y) const {
00538 assert((x >= 0) && (x < w) && (y >= 0) && (y < h));
00539 return _b[x+y*w];
00540 }
00542 void init(int x, int y) {
00543 if (b(x,y).min() == 0)
00544 b(x,y).init(*this,1,9);
00545 }
00547 template<class Data>
00548 void distinctlinear(Cache<Data>& dc, const IntVarArgs& x, int c,
00549 const SizeOptions& opt) {
00550 if (opt.model() == MODEL_DECOMPOSE) {
00551 distinct(*this, x, opt.icl());
00552 linear(*this, x, IRT_EQ, c, opt.icl());
00553 } else {
00554 int n=x.size();
00555 switch (n) {
00556 case 0:
00557 return;
00558 case 1:
00559 rel(*this, x[0], IRT_EQ, c);
00560 return;
00561 case 8:
00562
00563 rel(*this, x, IRT_NQ, 9*(9+1)/2 - c);
00564 break;
00565 case 9:
00566 break;
00567 default:
00568 if (c == n*(n+1)/2) {
00569
00570 rel(*this, x, IRT_LQ, n);
00571 } else if (c == n*(n+1)/2 + 1) {
00572
00573 rel(*this, x, IRT_LQ, n+1);
00574 rel(*this, x, IRT_NQ, n);
00575 } else if (c == 9*(9+1)/2 - (9-n)*(9-n+1)/2) {
00576
00577 rel(*this, x, IRT_GQ, 9-n+1);
00578 } else if (c == 9*(9+1)/2 - (9-n)*(9-n+1)/2 + 1) {
00579
00580 rel(*this, x, IRT_GQ, 9-n);
00581 rel(*this, x, IRT_NQ, 9-n+1);
00582 } else if (n == 2) {
00583
00584 IntArgs e(c);
00585 e[0]=0;
00586 for (int i=1; i<c; i++)
00587 e[i]=(c-i == i) ? 0 : c-i;
00588 element(*this, e, x[0], x[1]);
00589 return;
00590 } else {
00591 extensional(*this, x, dc.get(n,c));
00592 return;
00593 }
00594 }
00595 distinct(*this, x, opt.icl());
00596 }
00597 }
00599 Kakuro(const SizeOptions& opt)
00600 : w(examples[opt.size()][0]), h(examples[opt.size()][1]),
00601 _b(*this,w*h) {
00602 IntVar black(*this,0,0);
00603
00604
00605
00606 for (int i=w*h; i--; )
00607 _b[i] = black;
00608 const int* k = &examples[opt.size()][2];
00609
00610 Cache<DFA> dfa_cache;
00611
00612 Cache<TupleSet> ts_cache;
00613
00614 while (*k >= 0) {
00615 int x=*k++; int y=*k++; int n=*k++; int s=*k++;
00616 IntVarArgs col(n);
00617 for (int i=n; i--; ) {
00618 init(x,y+i+1); col[i]=b(x,y+i+1);
00619 }
00620 if (opt.propagation() == PROP_TUPLE_SET)
00621 distinctlinear(ts_cache,col,s,opt);
00622 else
00623 distinctlinear(dfa_cache,col,s,opt);
00624 }
00625 k++;
00626
00627 while (*k >= 0) {
00628 int x=*k++; int y=*k++; int n=*k++; int s=*k++;
00629 IntVarArgs row(n);
00630 for (int i=n; i--; ) {
00631 init(x+i+1,y); row[i]=b(x+i+1,y);
00632 }
00633 if (opt.propagation() == PROP_TUPLE_SET)
00634 distinctlinear(ts_cache,row,s,opt);
00635 else
00636 distinctlinear(dfa_cache,row,s,opt);
00637 }
00638 branch(*this, _b, INT_VAR_SIZE_MIN, INT_VAL_SPLIT_MIN);
00639 }
00641 Kakuro(bool share, Kakuro& s) : Script(share,s), w(s.w), h(s.h) {
00642 _b.update(*this, share, s._b);
00643 }
00645 virtual Space*
00646 copy(bool share) {
00647 return new Kakuro(share,*this);
00648 }
00650 virtual void
00651 print(std::ostream& os) const {
00652 for (int y=0; y<h; y++) {
00653 os << '\t';
00654 for (int x=0; x<w; x++)
00655 if (b(x,y).min() == 0)
00656 os << ". ";
00657 else
00658 os << b(x,y) << ' ';
00659 os << std::endl;
00660 }
00661 }
00662 };
00663
00664
00668 int
00669 main(int argc, char* argv[]) {
00670 SizeOptions opt("Kakuro");
00671 opt.propagation(Kakuro::PROP_TUPLE_SET);
00672 opt.propagation(Kakuro::PROP_DFA,
00673 "dfa","Use DFAs for storing combinations");
00674 opt.propagation(Kakuro::PROP_TUPLE_SET,
00675 "tuple-set","Use tuple sets for storing combinations");
00676
00677 opt.model(Kakuro::MODEL_COMBINE);
00678 opt.model(Kakuro::MODEL_DECOMPOSE,
00679 "decompose","decompose distinct and linear constraints");
00680 opt.model(Kakuro::MODEL_COMBINE,
00681 "combine","combine distinct and linear constraints");
00682
00683 opt.icl(ICL_DOM);
00684 opt.parse(argc,argv);
00685 if (opt.size() >= n_examples) {
00686 std::cerr << "Error: size must be between 0 and "
00687 << n_examples-1 << std::endl;
00688 return 1;
00689 }
00690 Script::run<Kakuro,DFS,SizeOptions>(opt);
00691 return 0;
00692 }
00693
00694