kakuro.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Contributing authors: 00007 * Mikael Lagerkvist <lagerkvist@gecode.org> 00008 * 00009 * Copyright: 00010 * Christian Schulte, 2007 00011 * Mikael Lagerkivst, 2007 00012 * 00013 * Last modified: 00014 * $Date: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00015 * $Revision: 11473 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 // Easy, Author: Casty 00072 const int k0[] = { 00073 // Dimension w x h 00074 12,10, 00075 // Vertical constraints 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 // Horizontal constraints 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 // Easy, Author: Ogawa Minori 00093 const int k1[] = { 00094 // Dimension w x h 00095 12,10, 00096 // Vertical constraints 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 // Horizontal constraints 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 // Easy, Author: SAKAMOTO, Nobuyuki 00114 const int k2[] = { 00115 // Dimension w x h 00116 12,10, 00117 // Vertical constraints 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 // Horizontal constraints 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 // Easy, Author: country mushroom 00134 const int k3[] = { 00135 // Dimension w x h 00136 12,10, 00137 // Vertical constraints 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 // Horizontal constraints 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 // Medium, Author: Komieda 00154 const int k4[] = { 00155 // Dimension w x h 00156 20,12, 00157 // Vertical constraints 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 // Horizontal constraints 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 // Medium, Author: crimson 00186 const int k5[] = { 00187 // Dimension w x h 00188 20,12, 00189 // Vertical constraints 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 // Horizontal constraints 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 // Hard, Author: Yuichi Saito 00220 const int k6[] = { 00221 // Dimension w x h 00222 20,12, 00223 // Vertical constraints 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 // Horizontal constraints 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 // Hard, Author: mimic 00253 const int k7[] = { 00254 // Dimension w x h 00255 22,14, 00256 // Vertical constraints 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 // Horizontal constraints 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 // Hard, Author: OX 00290 const int k8[] = { 00291 // Dimension w x h 00292 22,14, 00293 // Vertical constraints 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 // Horizontal constraints 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 // Hard, Author: TAKEI Daisuke 00329 const int k9[] = { 00330 // Dimension w x h 00331 22,14, 00332 // Vertical constraints 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 // Horizontal constraints 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 protected: 00379 IntVarArray x; 00380 public: 00382 DistinctLinear(int n, int s) : x(*this,n,1,9) { 00383 distinct(*this, x); 00384 linear(*this, x, IRT_EQ, s); 00385 branch(*this, x, INT_VAR_NONE, INT_VAL_SPLIT_MIN); 00386 } 00388 DistinctLinear(bool share, DistinctLinear& s) : Space(share,s) { 00389 x.update(*this, share, s.x); 00390 } 00392 virtual Space* 00393 copy(bool share) { 00394 return new DistinctLinear(share,*this); 00395 } 00397 IntArgs solution(void) const { 00398 IntArgs s(x.size()); 00399 for (int i=0; i<x.size(); i++) 00400 s[i]=x[i].val(); 00401 return s; 00402 } 00403 }; 00404 00408 TupleSet generate(int n, int c) { 00409 // Setup search engine that enumerates all solutions 00410 DistinctLinear* e = new DistinctLinear(n,c); 00411 DFS<DistinctLinear> d(e); 00412 delete e; 00413 TupleSet ts; 00414 while (DistinctLinear* s = d.next()) { 00415 ts.add(s->solution()); delete s; 00416 } 00417 ts.finalize(); 00418 return ts; 00419 } 00420 00424 class Cache { 00425 private: 00427 class Entry { 00428 public: 00429 int n; 00430 int c; 00431 TupleSet ts; 00432 Entry* next; 00433 }; 00434 Entry* cache; 00435 public: 00437 Cache(void) : cache(NULL) {} 00439 TupleSet get(int n, int c) { 00440 for (Entry* e = cache; e != NULL; e = e->next) 00441 if ((e->n == n) && (e->c == c)) 00442 return e->ts; 00443 Entry* e = new Entry; 00444 e->n = n; 00445 e->c = c; 00446 e->ts = generate(n,c); 00447 e->next = cache; 00448 cache = e; 00449 return cache->ts; 00450 } 00452 ~Cache(void) { 00453 Entry* e = cache; 00454 while (e != NULL) { 00455 Entry* d = e; 00456 e = e->next; 00457 delete d; 00458 } 00459 } 00460 }; 00461 00462 } 00463 00464 00475 class Kakuro : public Script { 00476 protected: 00477 const int w; 00478 const int h; 00479 IntVarArray f; 00480 public: 00482 enum { 00483 MODEL_DECOMPOSE, 00484 MODEL_COMBINE, 00485 }; 00487 IntVar init(IntVar& x) { 00488 if (x.min() == 0) 00489 x = IntVar(*this,1,9); 00490 return x; 00491 } 00493 void distinctlinear(Cache& dc, const IntVarArgs& x, int c, 00494 const SizeOptions& opt) { 00495 int n=x.size(); 00496 if (opt.model() == MODEL_DECOMPOSE) { 00497 if (n < 8) 00498 linear(*this, x, IRT_EQ, c, opt.icl()); 00499 else if (n == 8) 00500 rel(*this, x, IRT_NQ, 9*(9+1)/2 - c); 00501 distinct(*this, x, opt.icl()); 00502 } else { 00503 switch (n) { 00504 case 0: 00505 return; 00506 case 1: 00507 rel(*this, x[0], IRT_EQ, c); 00508 return; 00509 case 8: 00510 // Prune the single missing digit 00511 rel(*this, x, IRT_NQ, 9*(9+1)/2 - c); 00512 break; 00513 case 9: 00514 break; 00515 default: 00516 if (c == n*(n+1)/2) { 00517 // sum has unique decomposition: 1 + ... + n 00518 rel(*this, x, IRT_LQ, n); 00519 } else if (c == n*(n+1)/2 + 1) { 00520 // sum has unique decomposition: 1 + ... + n-1 + n+1 00521 rel(*this, x, IRT_LQ, n+1); 00522 rel(*this, x, IRT_NQ, n); 00523 } else if (c == 9*(9+1)/2 - (9-n)*(9-n+1)/2) { 00524 // sum has unique decomposition: (9-n+1) + (9-n+2) + ... + 9 00525 rel(*this, x, IRT_GQ, 9-n+1); 00526 } else if (c == 9*(9+1)/2 - (9-n)*(9-n+1)/2 + 1) { 00527 // sum has unique decomposition: (9-n) + (9-n+2) + ... + 9 00528 rel(*this, x, IRT_GQ, 9-n); 00529 rel(*this, x, IRT_NQ, 9-n+1); 00530 } else { 00531 extensional(*this, x, dc.get(n,c)); 00532 return; 00533 } 00534 } 00535 distinct(*this, x, opt.icl()); 00536 } 00537 } 00539 Kakuro(const SizeOptions& opt) 00540 : w(examples[opt.size()][0]), h(examples[opt.size()][1]), 00541 f(*this,w*h) { 00542 IntVar black(*this,0,0); 00543 // Initialize all fields as black (unused). Only if a field 00544 // is actually used in a constraint, create a fresh variable 00545 // for it (done via init). 00546 for (int i=w*h; i--; ) 00547 f[i] = black; 00548 00549 // Cache of already computed tuple sets 00550 Cache cache; 00551 00552 // Matrix for accessing board fields 00553 Matrix<IntVarArray> b(f,w,h); 00554 // Access to hints 00555 const int* k = &examples[opt.size()][2]; 00556 00557 // Process vertical hints 00558 while (*k >= 0) { 00559 int x=*k++; int y=*k++; int n=*k++; int s=*k++; 00560 IntVarArgs col(n); 00561 for (int i=n; i--; ) 00562 col[i]=init(b(x,y+i+1)); 00563 distinctlinear(cache,col,s,opt); 00564 } 00565 k++; 00566 00567 // Process horizontal hints 00568 while (*k >= 0) { 00569 int x=*k++; int y=*k++; int n=*k++; int s=*k++; 00570 IntVarArgs row(n); 00571 for (int i=n; i--; ) 00572 row[i]=init(b(x+i+1,y)); 00573 distinctlinear(cache,row,s,opt); 00574 } 00575 branch(*this, f, INT_VAR_SIZE_AFC_MIN, INT_VAL_SPLIT_MIN); 00576 } 00578 Kakuro(bool share, Kakuro& s) : Script(share,s), w(s.w), h(s.h) { 00579 f.update(*this, share, s.f); 00580 } 00582 virtual Space* 00583 copy(bool share) { 00584 return new Kakuro(share,*this); 00585 } 00587 virtual void 00588 print(std::ostream& os) const { 00589 Matrix<IntVarArray> b(f,w,h); 00590 for (int y=0; y<h; y++) { 00591 os << '\t'; 00592 for (int x=0; x<w; x++) 00593 if (b(x,y).min() == 0) 00594 os << ". "; 00595 else 00596 os << b(x,y) << ' '; 00597 os << std::endl; 00598 } 00599 } 00600 }; 00601 00602 00606 int 00607 main(int argc, char* argv[]) { 00608 SizeOptions opt("Kakuro"); 00609 opt.model(Kakuro::MODEL_COMBINE); 00610 opt.model(Kakuro::MODEL_DECOMPOSE, 00611 "decompose","decompose distinct and linear constraints"); 00612 opt.model(Kakuro::MODEL_COMBINE, 00613 "combine","combine distinct and linear constraints"); 00614 opt.icl(ICL_DOM); 00615 opt.parse(argc,argv); 00616 if (opt.size() >= n_examples) { 00617 std::cerr << "Error: size must be between 0 and " 00618 << n_examples-1 << std::endl; 00619 return 1; 00620 } 00621 Script::run<Kakuro,DFS,SizeOptions>(opt); 00622 return 0; 00623 } 00624 00625 // STATISTICS: example-any