Generated on Fri Oct 19 11:24:48 2018 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  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041 
00042 using namespace Gecode;
00043 
00044 namespace {
00045 
00066 
00067   // Easy, Author: Casty
00068   const int k0[] = {
00069     // Dimension w x h
00070     12,10,
00071     // Vertical constraints
00072      2, 0, 5,16,     3, 0, 2, 4,     5, 0, 3, 6,     6, 0, 2, 4,
00073      7, 0, 5,15,    10, 0, 3, 6,    11, 0, 3, 7,     1, 1, 3, 7,
00074      9, 1, 5,16,     4, 2, 2, 5,     8, 2, 2, 3,     3, 3, 5,16,
00075      6, 3, 3, 8,     5, 4, 5,15,    10, 4, 5,15,     4, 5, 2, 3,
00076      8, 5, 2, 4,    11, 5, 3, 7,     1, 6, 3, 6,     2, 6, 3, 7,
00077      7, 6, 3, 7,     6, 7, 2, 3,     9, 7, 2, 4,    -1,
00078     // Horizontal constraints
00079      1, 1, 2, 7,     4, 1, 3, 9,     9, 1, 2, 4,     0, 2, 3, 7,
00080      4, 2, 3, 7,     8, 2, 3, 6,     0, 3, 2, 3,     3, 3, 2, 4,
00081      6, 3, 5,16,     0, 4, 4,10,     5, 4, 4,10,     1, 5, 2,10,
00082      4, 5, 3, 6,     8, 5, 2, 5,     2, 6, 4,10,     7, 6, 4,12,
00083      0, 7, 5,16,     6, 7, 2, 4,     9, 7, 2, 4,     0, 8, 3, 7,
00084      4, 8, 3, 8,     8, 8, 3, 6,     0, 9, 2, 3,     4, 9, 3, 7,
00085      8, 9, 2, 3,    -1
00086   };
00087 
00088   // Easy, Author: Ogawa Minori
00089   const int k1[] = {
00090     // Dimension w x h
00091     12,10,
00092     // Vertical constraints
00093      1, 0, 2, 4,     2, 0, 5,15,     5, 0, 5,18,     6, 0, 2,12,
00094      7, 0, 3, 8,    10, 0, 3,24,    11, 0, 3,23,     3, 1, 2, 7,
00095      9, 1, 3,24,     4, 2, 5,16,     8, 2, 5,35,     1, 3, 2,12,
00096      6, 3, 3,17,     7, 4, 5,34,    10, 4, 5,34,    11, 4, 2,16,
00097      3, 5, 3, 6,     1, 6, 3, 7,     2, 6, 3, 6,     5, 6, 3,23,
00098      9, 6, 2,10,     6, 7, 2,14,    11, 7, 2,10,    -1,
00099     // Horizontal constraints
00100      0, 1, 2, 3,     4, 1, 3,15,     9, 1, 2,16,     0, 2, 3, 6,
00101      4, 2, 3, 7,     8, 2, 3,24,     1, 3, 4,11,     6, 3, 5,34,
00102      0, 4, 2,14,     3, 4, 3,23,     7, 4, 2,14,     0, 5, 2, 7,
00103      3, 5, 5,15,     9, 5, 2,17,     2, 6, 2, 6,     5, 6, 3,23,
00104      9, 6, 2,13,     0, 7, 5,16,     6, 7, 4,30,     0, 8, 3, 6,
00105      4, 8, 3,23,     8, 8, 3, 7,     0, 9, 2, 4,     4, 9, 3,24,
00106      9, 9, 2,17,    -1
00107   };
00108 
00109   // Easy, Author: SAKAMOTO, Nobuyuki
00110   const int k2[] = {
00111     // Dimension w x h
00112     12,10,
00113     // Vertical constraints
00114      2, 0, 5,15,     3, 0, 2, 3,     7, 0, 3, 7,     8, 0, 4,23,
00115      9, 0, 2,12,    10, 0, 3,20,    11, 0, 3, 9,     4, 1, 3, 7,
00116      5, 1, 4,10,     1, 2, 3, 6,     6, 2, 5,15,     9, 3, 2,16,
00117      3, 4, 2, 3,     7, 4, 4,13,    10, 4, 5,35,    11, 4, 3,23,
00118      4, 5, 4,11,     8, 5, 3,23,     1, 6, 3,23,     2, 6, 3,14,
00119      5, 6, 3,11,     3, 7, 2,13,     9, 7, 2,17,    -1,
00120     // Horizontal constraints
00121      1, 1, 2, 4,     6, 1, 5,15,     1, 2, 4,11,     6, 2, 5,34,
00122      0, 3, 2, 3,     3, 3, 5,15,     9, 3, 2,10,     0, 4, 2, 4,
00123      3, 4, 3, 6,     7, 4, 2,17,     0, 5, 3, 7,     4, 5, 3, 8,
00124      8, 5, 3,18,     2, 6, 2, 3,     5, 6, 3,11,     9, 6, 2,16,
00125      0, 7, 2,16,     3, 7, 5,16,     9, 7, 2,17,     0, 8, 5,16,
00126      6, 8, 4,30,     0, 9, 5,35,     8, 9, 2,17,    -1
00127   };
00128 
00129   // Easy, Author: country mushroom
00130   const int k3[] = {
00131     // Dimension w x h
00132     12,10,
00133     // Vertical constraints
00134      3, 0, 3, 7,     4, 0, 6,21,     7, 0, 4,29,     8, 0, 2,17,
00135     10, 0, 4,29,    11, 0, 3,23,     2, 1, 3, 6,     6, 1, 2,16,
00136      9, 1, 4,14,     1, 2, 2, 4,     5, 2, 2, 3,     8, 3, 6,22,
00137      3, 4, 4,10,     2, 5, 4,11,     5, 5, 4,10,     7, 5, 2,10,
00138     10, 5, 3,24,    11, 5, 2,16,     1, 6, 3, 7,     6, 6, 2, 9,
00139      9, 6, 3,23,     4, 7, 2, 4,    -1,
00140     // Horizontal constraints
00141      2, 1, 2, 4,     6, 1, 2,17,     9, 1, 2,16,     1, 2, 3, 6,
00142      5, 2, 6,39,     0, 3, 7,28,     8, 3, 3,24,     0, 4, 2, 3,
00143      3, 4, 2, 3,     6, 4, 4,20,     2, 5, 2, 9,     7, 5, 2, 4,
00144      1, 6, 4,10,     6, 6, 2, 3,     9, 6, 2,16,     0, 7, 3, 6,
00145      4, 7, 7,42,     0, 8, 6,21,     7, 8, 3,21,     0, 9, 2, 4,
00146      3, 9, 2, 3,     7, 9, 2,16,    -1
00147   };
00148 
00149   // Medium, Author: Komieda
00150   const int k4[] = {
00151     // Dimension w x h
00152     20,12,
00153     // Vertical constraints
00154      3, 0, 3,21,     4, 0, 2, 4,     5, 0, 4,11,     8, 0, 2, 8,
00155      9, 0, 3, 7,    11, 0, 2, 3,    12, 0, 3, 6,    15, 0, 6,39,
00156     16, 0, 2, 3,    17, 0, 3,23,     2, 1, 5,15,     6, 1, 4,10,
00157     10, 1, 4,11,    14, 1, 4,11,    18, 1, 3, 6,     1, 2, 3,24,
00158      7, 2, 4,14,    13, 2, 2,10,    19, 2, 2,16,     4, 3, 5,18,
00159      8, 3, 4,10,    11, 3, 4,12,    16, 3, 5,33,     3, 4, 3,23,
00160      9, 4, 4,29,    12, 4, 4,30,    17, 4, 3,18,     5, 5, 6,38,
00161     13, 5, 4,29,    18, 5, 5,15,     6, 6, 4,25,    10, 6, 4,12,
00162     14, 6, 4,28,    19, 6, 3,21,     1, 7, 2, 4,     2, 7, 3, 7,
00163      7, 7, 2, 7,    15, 7, 4,11,     3, 8, 3,19,     8, 8, 3,24,
00164     11, 8, 3, 7,    17, 8, 3, 6,     4, 9, 2,16,     9, 9, 2,16,
00165     12, 9, 2,17,    16, 9, 2, 5,    -1,
00166     // Horizontal constraints
00167      2, 1, 3, 7,     7, 1, 2, 4,    10, 1, 2, 4,    14, 1, 3,19,
00168      1, 2, 5,18,     7, 2, 5,15,    13, 2, 5,16,     0, 3, 3,21,
00169      4, 3, 3, 6,     8, 3, 2, 3,    11, 3, 4,11,    16, 3, 3,20,
00170      0, 4, 2,14,     3, 4, 5,15,     9, 4, 2, 3,    12, 4, 4,29,
00171     17, 4, 2, 8,     0, 5, 4,27,     5, 5, 7,42,    13, 5, 4,12,
00172      1, 6, 4,12,     6, 6, 3, 8,    10, 6, 3,20,    14, 6, 4,29,
00173      2, 7, 4,28,     7, 7, 7,28,    15, 7, 4,28,     0, 8, 2, 3,
00174      3, 8, 4,11,     8, 8, 2,10,    11, 8, 5,35,    17, 8, 2,10,
00175      0, 9, 3, 6,     4, 9, 4,30,     9, 9, 2, 3,    12, 9, 3,19,
00176     16, 9, 3, 7,     1,10, 5,34,     7,10, 5,34,    13,10, 5,17,
00177      2,11, 3,23,     7,11, 2,17,    10,11, 2,10,    14,11, 3, 6,
00178     -1
00179   };
00180 
00181   // Medium, Author: crimson
00182   const int k5[] = {
00183     // Dimension w x h
00184     20,12,
00185     // Vertical constraints
00186      1, 0, 2, 3,     2, 0, 5,33,     4, 0, 2, 8,     5, 0, 4,14,
00187      7, 0, 5,15,     8, 0, 3,19,     9, 0, 2,12,    11, 0, 4,11,
00188     12, 0, 2, 4,    13, 0, 5,16,    15, 0, 4,11,    16, 0, 2,17,
00189     18, 0, 5,34,    19, 0, 2,17,     3, 1, 2, 3,    10, 1, 9,45,
00190     17, 1, 2,16,     6, 2, 3,20,    14, 2, 3,12,     1, 3, 2,13,
00191      4, 3, 5,33,     9, 3, 3,20,    16, 3, 5,21,    19, 3, 2, 8,
00192      3, 4, 3,11,     8, 4, 3,11,    12, 4, 3, 7,    17, 4, 3, 8,
00193     11, 5, 3,23,     1, 6, 2,11,     2, 6, 5,15,     6, 6, 3,23,
00194      7, 6, 5,27,    13, 6, 5,30,    14, 6, 3, 7,    18, 6, 5,15,
00195     19, 6, 2, 3,     5, 7, 4,26,     9, 7, 4,27,    15, 7, 4,27,
00196      3, 8, 2, 7,    12, 8, 3,24,    17, 8, 2,17,     1, 9, 2, 5,
00197      4, 9, 2, 9,     8, 9, 2, 3,    11, 9, 2,16,    16, 9, 2,16,
00198     19, 9, 2,10,    -1,
00199     // Horizontal constraints
00200      0, 1, 2, 4,     3, 1, 2, 7,     6, 1, 3, 7,    10, 1, 3, 7,
00201     14, 1, 2,11,    17, 1, 2,16,     0, 2, 5,16,     6, 2, 7,42,
00202     14, 2, 5,35,     1, 3, 2,10,     4, 3, 4,15,     9, 3, 2, 6,
00203     12, 3, 3, 7,    16, 3, 2,13,     0, 4, 2,17,     3, 4, 4,29,
00204      8, 4, 3,19,    12, 4, 4,11,    17, 4, 2, 9,     0, 5, 4,29,
00205      5, 5, 5,33,    11, 5, 3, 6,    15, 5, 4,29,     2, 6, 2, 4,
00206      7, 6, 5,16,    15, 6, 2, 4,     0, 7, 4,12,     5, 7, 3,10,
00207      9, 7, 5,18,    15, 7, 4,12,     0, 8, 2,13,     3, 8, 4,29,
00208      8, 8, 3,24,    12, 8, 4,23,    17, 8, 2, 5,     1, 9, 2, 6,
00209      4, 9, 3,24,     8, 9, 2, 4,    11, 9, 4,28,    16, 9, 2,11,
00210      0,10, 5,15,     6,10, 7,41,    14,10, 5,34,     0,11, 2, 3,
00211      3,11, 2,17,     6,11, 3,14,    10,11, 3,23,    14,11, 2,11,
00212     17,11, 2, 4,    -1
00213   };
00214 
00215   // Hard, Author: Yuichi Saito
00216   const int k6[] = {
00217     // Dimension w x h
00218     20,12,
00219     // Vertical constraints
00220      1, 0, 2, 6,     2, 0, 2,16,     4, 0, 3,10,     5, 0, 2,12,
00221      9, 0, 7,28,    10, 0, 2,12,    11, 0, 3,24,    15, 0, 3,10,
00222     16, 0, 2,17,    17, 0, 6,22,     3, 1, 3,18,     6, 1, 4,10,
00223      8, 1, 2, 8,    12, 1, 2,10,    13, 1, 3,18,    18, 1, 3,12,
00224      7, 2, 4,11,    14, 2, 3, 7,    19, 2, 2, 7,     1, 3, 2, 8,
00225      2, 3, 3, 7,     5, 3, 4,25,    10, 3, 2, 4,    16, 3, 4,15,
00226      4, 4, 4,11,    11, 4, 7,42,    12, 4, 2,17,    15, 4, 4,26,
00227      3, 5, 6,22,     8, 5, 2,16,    13, 5, 4,30,    18, 5, 3,24,
00228      6, 6, 3, 7,    10, 6, 2, 4,    14, 6, 4,29,    19, 6, 2,14,
00229      1, 7, 2,16,     2, 7, 3,11,     7, 7, 3,24,    17, 7, 3,21,
00230      5, 8, 3,23,     8, 8, 2,12,     9, 8, 3,20,    12, 8, 2,17,
00231     16, 8, 3, 6,     4, 9, 2, 9,    10, 9, 2,16,    15, 9, 2, 9,
00232     18, 9, 2, 3,    19, 9, 2,12,    -1,
00233     // Horizontal constraints
00234      0, 1, 2,10,     3, 1, 2, 5,     8, 1, 3,23,    14, 1, 3,11,
00235      0, 2, 6,38,     7, 2, 6,39,    14, 2, 4,30,     2, 3, 2,10,
00236      5, 3, 4,11,    10, 3, 5,18,    16, 3, 3, 7,     0, 4, 3, 7,
00237      4, 4, 3, 7,     8, 4, 2, 6,    12, 4, 2, 8,    15, 4, 4,11,
00238      0, 5, 2, 8,     3, 5, 4,14,     8, 5, 4,24,    13, 5, 4,10,
00239      1, 6, 4,13,     6, 6, 3,14,    10, 6, 3,19,    14, 6, 4,29,
00240      2, 7, 4,15,     7, 7, 4,14,    12, 7, 4,29,    17, 7, 2,16,
00241      0, 8, 4,29,     5, 8, 2,13,     9, 8, 2, 8,    12, 8, 3,23,
00242     16, 8, 3,22,     0, 9, 3,10,     4, 9, 5,32,    10, 9, 4,29,
00243     15, 9, 2,10,     1,10, 4,14,     6,10, 6,39,    13,10, 6,22,
00244      2,11, 3,21,     8,11, 3,23,    14,11, 2, 6,    17,11, 2,11,
00245     -1
00246   };
00247 
00248   // Hard, Author: mimic
00249   const int k7[] = {
00250     // Dimension w x h
00251     22,14,
00252     // Vertical constraints
00253      1, 0, 3,23,     2, 0, 4,29,     3, 0, 2,16,     7, 0, 2, 7,
00254      8, 0, 2,10,     9, 0, 5,30,    13, 0, 7,41,    14, 0, 2,16,
00255     15, 0, 4,29,    17, 0, 2, 3,    18, 0, 6,21,    20, 0, 3, 7,
00256     21, 0, 2, 4,     4, 1, 5,35,     6, 1, 2, 4,    10, 1, 2,17,
00257     12, 1, 3,24,    19, 1, 9,45,     5, 2, 3,23,    11, 2, 9,45,
00258     16, 2, 4,21,     3, 3, 9,45,     7, 3, 5,15,     8, 3, 4,10,
00259     14, 3, 2,10,    17, 3, 2, 3,     6, 4, 2, 4,    10, 4, 4,30,
00260     20, 4, 4,11,     2, 5, 4,13,    12, 5, 4,30,    15, 5, 5,35,
00261     21, 5, 2, 4,     1, 6, 2, 4,     9, 6, 7,41,    14, 6, 4,29,
00262      4, 7, 6,38,     6, 7, 4,11,    16, 7, 2,16,    18, 7, 5,15,
00263      5, 8, 2, 9,     8, 8, 2,17,    13, 8, 5,16,    17, 8, 3, 7,
00264      7, 9, 4,20,    10, 9, 3,23,    20, 9, 4,12,     2,10, 3,23,
00265     12,10, 2, 6,    16,10, 2, 4,    21,10, 3, 9,     1,11, 2,16,
00266      5,11, 2,16,     8,11, 2,16,    14,11, 2, 6,    15,11, 2, 4,
00267     19,11, 2, 4,    -1,
00268     // Horizontal constraints
00269      0, 1, 3,23,     6, 1, 3, 8,    12, 1, 3,23,    16, 1, 2, 4,
00270     19, 1, 2, 4,     0, 2, 4,30,     5, 2, 5,31,    11, 2, 4,29,
00271     16, 2, 5,15,     0, 3, 2,16,     3, 3, 3,19,     8, 3, 5,32,
00272     14, 3, 2,17,    17, 3, 3, 8,     1, 4, 4,29,     6, 4, 3, 9,
00273     10, 4, 9,45,     2, 5, 9,45,    12, 5, 2,17,    15, 5, 5,16,
00274      1, 6, 3,24,     5, 6, 3, 6,     9, 6, 4,30,    14, 6, 2,16,
00275     17, 6, 4,11,     0, 7, 3, 7,     6, 7, 9,45,    18, 7, 3, 7,
00276      0, 8, 4,11,     5, 8, 2, 4,     8, 8, 4,29,    13, 8, 3,23,
00277     17, 8, 3, 7,     1, 9, 5,16,     7, 9, 2,17,    10, 9, 9,45,
00278      2,10, 9,45,    12,10, 3,23,    16,10, 4,14,     1,11, 3,24,
00279      5,11, 2, 6,     8,11, 5,16,    15,11, 3, 7,    19,11, 2, 8,
00280      0,12, 5,35,     6,12, 4,30,    11,12, 5,15,    17,12, 4,11,
00281      0,13, 2,17,     3,13, 2,16,     6,13, 3,24,    12,13, 3, 6,
00282     18,13, 3, 7,    -1
00283   };
00284 
00285   // Hard, Author: OX
00286   const int k8[] = {
00287     // Dimension w x h
00288     22,14,
00289     // Vertical constraints
00290      1, 0, 2, 4,     2, 0, 5,15,     5, 0, 5,16,     6, 0, 2,10,
00291      7, 0, 3,18,     8, 0, 4,29,    10, 0, 5,16,    11, 0, 2, 6,
00292     13, 0, 2, 8,    14, 0, 5,16,    15, 0, 6,38,    18, 0, 5,15,
00293     19, 0, 2, 8,    20, 0, 3, 7,    21, 0, 3, 8,     3, 1, 9,45,
00294     16, 1, 2, 4,     4, 2, 2, 3,     9, 2, 8,39,    17, 2, 2, 3,
00295      1, 3, 2, 5,     6, 3, 6,22,    11, 3, 3,22,    13, 3, 8,38,
00296     19, 3, 9,45,     7, 4, 2, 4,    12, 4, 3,24,    16, 4, 6,38,
00297     20, 4, 3,24,     4, 5, 2,16,     8, 5, 2,14,    17, 5, 2,16,
00298     21, 5, 2,11,     1, 6, 2, 4,     2, 6, 3, 8,     5, 6, 2, 7,
00299     10, 6, 3,18,    14, 6, 2,16,    18, 6, 2,16,     7, 7, 6,22,
00300     11, 7, 3, 7,    15, 7, 2,15,     4, 8, 5,35,     8, 8, 5,34,
00301     12, 8, 5,34,    17, 8, 5,34,    20, 8, 5,34,    21, 8, 2, 3,
00302      5, 9, 2,16,    14, 9, 4,12,    18, 9, 2, 7,     1,10, 3,23,
00303      2,10, 3,21,     6,10, 2, 9,    15,10, 3,20,     3,11, 2,17,
00304      9,11, 2, 4,    11,11, 2, 4,    16,11, 2,10,    21,11, 2,16,
00305     -1,
00306     // Horizontal constraints
00307      0, 1, 2, 6,     4, 1, 4,30,     9, 1, 2, 6,    12, 1, 3,10,
00308     17, 1, 4,12,     0, 2, 3, 8,     4, 2, 4,11,     9, 2, 2, 4,
00309     12, 2, 4,20,    17, 2, 4,11,     1, 3, 4,12,     6, 3, 4,28,
00310     13, 3, 5,15,    19, 3, 2, 5,     0, 4, 6,22,     7, 4, 4,28,
00311     12, 4, 3, 8,    16, 4, 3, 6,     0, 5, 3, 7,     4, 5, 3, 7,
00312      8, 5, 8,40,    17, 5, 3,22,     2, 6, 2, 8,     5, 6, 4,12,
00313     10, 6, 3,23,    14, 6, 3,22,    18, 6, 3,22,     0, 7, 6,38,
00314      7, 7, 3,24,    11, 7, 3,23,    15, 7, 6,39,     0, 8, 3, 6,
00315      4, 8, 3, 6,     8, 8, 3, 6,    12, 8, 4,29,    17, 8, 2,14,
00316      1, 9, 3,18,     5, 9, 8,36,    14, 9, 3,22,    18, 9, 3,10,
00317      2,10, 3,22,     6,10, 3,24,    10,10, 4,10,    15,10, 6,21,
00318      0,11, 2,16,     3,11, 5,34,    11,11, 4,29,    16,11, 4,30,
00319      0,12, 4,29,     5,12, 4,12,    10,12, 2,10,    13,12, 4,10,
00320     18,12, 3,23,     0,13, 4,28,     6,13, 3, 7,    10,13, 2,11,
00321     13,13, 4,28,    19,13, 2,13,    -1
00322   };
00323 
00324   // Hard, Author: TAKEI Daisuke
00325   const int k9[] = {
00326     // Dimension w x h
00327     22,14,
00328     // Vertical constraints
00329      1, 0, 4,10,     2, 0, 4,24,     3, 0, 3, 7,     7, 0, 3, 8,
00330      8, 0, 2,17,     9, 0, 3,13,    13, 0, 3,22,    14, 0, 2,12,
00331     15, 0, 3,24,    19, 0, 3,19,    20, 0, 4,28,    21, 0, 4,14,
00332      4, 1, 5,16,     6, 1, 5,17,    10, 1, 5,32,    12, 1, 5,34,
00333     16, 1, 5,35,    18, 1, 5,31,     5, 2, 3, 9,    11, 2, 3, 7,
00334     17, 2, 3, 7,     3, 4, 5,27,     7, 4, 5,16,     9, 4, 5,20,
00335     13, 4, 5,30,    15, 4, 5,30,    19, 4, 5,26,     1, 5, 3,12,
00336      2, 5, 3,20,     8, 5, 3,22,    14, 5, 3, 9,    20, 5, 3,10,
00337     21, 5, 3,20,     4, 7, 5,31,     6, 7, 5,16,    10, 7, 5,17,
00338     12, 7, 5,32,    16, 7, 5,19,    18, 7, 5,34,     5, 8, 3, 8,
00339     11, 8, 3,24,    17, 8, 3,24,     1, 9, 4,10,     2, 9, 4,15,
00340     20, 9, 4,30,    21, 9, 4,12,     3,10, 3,20,     7,10, 3, 6,
00341      9,10, 3, 9,    13,10, 3, 6,    15,10, 3, 7,    19,10, 3,24,
00342      8,11, 2, 8,    14,11, 2, 7,    -1,
00343     // Horizontal constraints
00344      0, 1, 3, 7,     6, 1, 3,12,    12, 1, 3,23,    18, 1, 3,23,
00345      0, 2, 4,11,     5, 2, 5,19,    11, 2, 5,33,    17, 2, 4,28,
00346      0, 3, 7,28,     8, 3, 5,34,    14, 3, 7,29,     0, 4, 2,12,
00347      3, 4, 3, 7,     9, 4, 3,16,    15, 4, 3,10,    19, 4, 2,10,
00348      2, 5, 5,18,     8, 5, 5,20,    14, 5, 5,29,     0, 6, 4,24,
00349      5, 6, 5,35,    11, 6, 5,23,    17, 6, 4,26,     0, 7, 3,23,
00350      6, 7, 3, 9,    12, 7, 3,10,    18, 7, 3,23,     0, 8, 4,15,
00351      5, 8, 5,19,    11, 8, 5,33,    17, 8, 4,10,     2, 9, 5,19,
00352      8, 9, 5,35,    14, 9, 5,31,     0,10, 2, 4,     3,10, 3,10,
00353      9,10, 3,18,    15,10, 3,24,    19,10, 2,12,     0,11, 7,41,
00354      8,11, 5,23,    14,11, 7,36,     0,12, 4,14,     5,12, 5,17,
00355     11,12, 5,15,    17,12, 4,26,     0,13, 3, 7,     6,13, 3, 7,
00356     12,13, 3, 6,    18,13, 3,23,    -1
00357   };
00359 
00361   const int* examples[] = {
00362     &k0[0], &k1[0], &k2[0], &k3[0], &k4[0],
00363     &k5[0], &k6[0], &k7[0], &k8[0], &k9[0]
00364   };
00366   const unsigned int n_examples = sizeof(examples)/sizeof(const int*);
00367 
00368 
00372   class DistinctLinear : public Space {
00373   protected:
00375     IntVarArray x;
00376   public:
00378     DistinctLinear(int n, int s) : x(*this,n,1,9) {
00379       distinct(*this, x);
00380       linear(*this, x, IRT_EQ, s);
00381       branch(*this, x, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
00382     }
00384     DistinctLinear(DistinctLinear& s) : Space(s) {
00385       x.update(*this, s.x);
00386     }
00388     virtual Space*
00389     copy(void) {
00390       return new DistinctLinear(*this);
00391     }
00393     IntArgs solution(void) const {
00394       IntArgs s(x.size());
00395       for (int i=0; i<x.size(); i++)
00396         s[i]=x[i].val();
00397       return s;
00398     }
00399   };
00400 
00404   TupleSet generate(int n, int c) {
00405     // Setup search engine that enumerates all solutions
00406     DistinctLinear* e = new DistinctLinear(n,c);
00407     DFS<DistinctLinear> d(e);
00408     delete e;
00409     TupleSet ts(n);
00410     while (DistinctLinear* s = d.next()) {
00411       ts.add(s->solution()); delete s;
00412     }
00413     ts.finalize();
00414     return ts;
00415   }
00416 
00420   class Cache {
00421   private:
00423     class Entry {
00424     public:
00425       int n;       
00426       int c;       
00427       TupleSet ts; 
00428       Entry* next; 
00429     };
00430     Entry* cache; 
00431   public:
00433     Cache(void) : cache(NULL) {}
00435     TupleSet get(int n, int c) {
00436       for (Entry* e = cache; e != NULL; e = e->next)
00437         if ((e->n == n) && (e->c == c))
00438           return e->ts;
00439       {
00440         Entry* e = new Entry;
00441         e->n = n;
00442         e->c = c;
00443         e->ts = generate(n,c);
00444         e->next = cache;
00445         cache = e;
00446       }
00447       return cache->ts;
00448     }
00450     ~Cache(void) {
00451       Entry* e = cache;
00452       while (e != NULL) {
00453         Entry* d = e;
00454         e = e->next;
00455         delete d;
00456       }
00457     }
00458   };
00459 
00460 }
00461 
00462 
00473 class Kakuro : public Script {
00474 protected:
00475   const int w;   
00476   const int h;   
00477   IntVarArray f; 
00478 public:
00480   enum {
00481     MODEL_DECOMPOSE,
00482     MODEL_COMBINE,  
00483   };
00485   IntVar init(IntVar& x) {
00486     if (x.min() == 0)
00487       x = IntVar(*this,1,9);
00488     return x;
00489   }
00491   void distinctlinear(Cache& dc, const IntVarArgs& x, int c,
00492                       const SizeOptions& opt) {
00493     int n=x.size();
00494     if (opt.model() == MODEL_DECOMPOSE) {
00495       if (n < 8)
00496         linear(*this, x, IRT_EQ, c, opt.ipl());
00497       else if (n == 8)
00498         rel(*this, x, IRT_NQ, 9*(9+1)/2 - c);
00499       distinct(*this, x, opt.ipl());
00500     } else {
00501       switch (n) {
00502       case 0:
00503         return;
00504       case 1:
00505         rel(*this, x[0], IRT_EQ, c);
00506         return;
00507       case 8:
00508         // Prune the single missing digit
00509         rel(*this, x, IRT_NQ, 9*(9+1)/2 - c);
00510         break;
00511       case 9:
00512         break;
00513       default:
00514         if (c == n*(n+1)/2) {
00515           // sum has unique decomposition: 1 + ... + n
00516           rel(*this, x, IRT_LQ, n);
00517         } else if (c == n*(n+1)/2 + 1) {
00518           // sum has unique decomposition: 1 + ... + n-1 + n+1
00519           rel(*this, x, IRT_LQ, n+1);
00520           rel(*this, x, IRT_NQ, n);
00521         } else if (c == 9*(9+1)/2 - (9-n)*(9-n+1)/2) {
00522           // sum has unique decomposition: (9-n+1) + (9-n+2) + ... + 9
00523           rel(*this, x, IRT_GQ, 9-n+1);
00524         } else if (c == 9*(9+1)/2 - (9-n)*(9-n+1)/2 + 1) {
00525           // sum has unique decomposition: (9-n) + (9-n+2) + ... + 9
00526           rel(*this, x, IRT_GQ, 9-n);
00527           rel(*this, x, IRT_NQ, 9-n+1);
00528         } else {
00529           extensional(*this, x, dc.get(n,c));
00530           return;
00531         }
00532       }
00533       distinct(*this, x, opt.ipl());
00534     }
00535   }
00537   Kakuro(const SizeOptions& opt)
00538     : Script(opt),
00539       w(examples[opt.size()][0]),  h(examples[opt.size()][1]),
00540       f(*this,w*h) {
00541     IntVar black(*this,0,0);
00542     // Initialize all fields as black (unused). Only if a field
00543     // is actually used in a constraint, create a fresh variable
00544     // for it (done via init).
00545     for (int i=w*h; i--; )
00546       f[i] = black;
00547 
00548     // Cache of already computed tuple sets
00549     Cache cache;
00550 
00551     // Matrix for accessing board fields
00552     Matrix<IntVarArray> b(f,w,h);
00553     // Access to hints
00554     const int* k = &examples[opt.size()][2];
00555 
00556     // Process vertical hints
00557     while (*k >= 0) {
00558       int x=*k++; int y=*k++; int n=*k++; int s=*k++;
00559       IntVarArgs col(n);
00560       for (int i=n; i--; )
00561         col[i]=init(b(x,y+i+1));
00562       distinctlinear(cache,col,s,opt);
00563     }
00564     k++;
00565 
00566     // Process horizontal hints
00567     while (*k >= 0) {
00568       int x=*k++; int y=*k++; int n=*k++; int s=*k++;
00569       IntVarArgs row(n);
00570       for (int i=n; i--; )
00571         row[i]=init(b(x+i+1,y));
00572       distinctlinear(cache,row,s,opt);
00573     }
00574     branch(*this, f, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_SPLIT_MIN());
00575   }
00577   Kakuro(Kakuro& s) : Script(s), w(s.w), h(s.h) {
00578     f.update(*this, s.f);
00579   }
00581   virtual Space*
00582   copy(void) {
00583     return new Kakuro(*this);
00584   }
00586   virtual void
00587   print(std::ostream& os) const {
00588     Matrix<IntVarArray> b(f,w,h);
00589     for (int y=0; y<h; y++) {
00590       os << '\t';
00591       for (int x=0; x<w; x++)
00592         if (b(x,y).min() == 0)
00593           os << ". ";
00594         else
00595           os << b(x,y) << ' ';
00596       os << std::endl;
00597     }
00598   }
00599 };
00600 
00601 
00605 int
00606 main(int argc, char* argv[]) {
00607   SizeOptions opt("Kakuro");
00608   opt.model(Kakuro::MODEL_COMBINE);
00609   opt.model(Kakuro::MODEL_DECOMPOSE,
00610                   "decompose","decompose distinct and linear constraints");
00611   opt.model(Kakuro::MODEL_COMBINE,
00612                   "combine","combine distinct and linear constraints");
00613   opt.ipl(IPL_DOM);
00614   opt.parse(argc,argv);
00615   if (opt.size() >= n_examples) {
00616     std::cerr << "Error: size must be between 0 and "
00617               << n_examples-1 << std::endl;
00618     return 1;
00619   }
00620   Script::run<Kakuro,DFS,SizeOptions>(opt);
00621   return 0;
00622 }
00623 
00624 // STATISTICS: example-any