Generated on Mon May 10 06:46:29 2010 for Gecode by doxygen 1.6.3

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-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00015  *     $Revision: 10684 $
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   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     // Setup search engine that enumerates all solutions
00410     DistinctLinear* e = new DistinctLinear(n,c);
00411     DFS<DistinctLinear> d(e);
00412     delete e;
00413     // Remember in \a ts the previous transitions
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     // Record all transitions in \a ts_all
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       // Skip common prefix
00425       for (; ts[i].symbol == s->x[i].val(); i++) {}
00426       // Generate transitions for new suffix
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       // Fix final state to 1
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     // Setup search engine that enumerates all solutions
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         // Prune the single missing digit
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           // sum has unique decomposition: 1 + ... + n
00570           rel(*this, x, IRT_LQ, n);
00571         } else if (c == n*(n+1)/2 + 1) {
00572           // sum has unique decomposition: 1 + ... + n-1 + n+1
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           // sum has unique decomposition: (9-n+1) + (9-n+2) + ... + 9
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           // sum has unique decomposition: (9-n) + (9-n+2) + ... + 9
00580           rel(*this, x, IRT_GQ, 9-n);
00581           rel(*this, x, IRT_NQ, 9-n+1);
00582         } else if (n == 2) {
00583           // Just use element constraint with no two equal digits
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     // Initialize all fields as black (unused). Only if a field
00604     // is actually used in a constraint, create a fresh variable
00605     // for it (done via init).
00606     for (int i=w*h; i--; )
00607       _b[i] = black;
00608     const int* k = &examples[opt.size()][2];
00609     // Cache of computed DFAs
00610     Cache<DFA> dfa_cache;
00611     // Cache of compute tuple sets
00612     Cache<TupleSet> ts_cache;
00613     // Process vertical constraints
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     // Process horizontal constraints
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 // STATISTICS: example-any