Generated on Wed Jul 27 2011 15:08:33 for Gecode by doxygen 1.7.4
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