Generated on Thu Apr 11 13:58:53 2019 for Gecode by doxygen 1.6.3

sudoku.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *     Guido Tack <tack@gecode.org>
00006  *     Christian Schulte <schulte@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Mikael Lagerkvist, 2005
00010  *     Guido Tack, 2005
00011  *     Christian Schulte, 2005
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 #include <string>
00043 #include <cmath>
00044 #include <cctype>
00045 
00046 using namespace Gecode;
00047 
00048 #include <examples/sudoku-instances.hh>
00049 
00055 class Sudoku : public Script {
00056 protected:
00058   const int n;
00060   IntVarArray x;
00061 public:
00062 
00064   Sudoku(const SizeOptions& opt)
00065     : Script(opt),
00066       n(example_size(examples[opt.size()])),
00067       x(*this, n*n*n*n, 1, n*n) {
00068 
00069     const int nn = n*n;
00070     Matrix<IntVarArray> m(x, nn, nn);
00071 
00072     // Constraints for rows and columns
00073     for (int i=0; i<nn; i++) {
00074       distinct(*this, m.row(i), opt.ipl());
00075       distinct(*this, m.col(i), opt.ipl());
00076     }
00077 
00078     // Constraints for squares
00079     for (int i=0; i<nn; i+=n) {
00080       for (int j=0; j<nn; j+=n) {
00081         distinct(*this, m.slice(i, i+n, j, j+n), opt.ipl());
00082       }
00083     }
00084 
00085     // Fill-in predefined fields
00086     for (int i=0; i<nn; i++)
00087       for (int j=0; j<nn; j++)
00088         if (int v = sudokuField(examples[opt.size()], nn, i, j))
00089           rel(*this, m(i,j), IRT_EQ, v );
00090 
00091     branch(*this, x, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
00092   }
00093 
00095   Sudoku(Sudoku& s) : Script(s), n(s.n) {
00096     x.update(*this, s.x);
00097   }
00098 
00100   virtual Space*
00101   copy(void) {
00102     return new Sudoku(*this);
00103   }
00104 
00106   virtual void
00107   print(std::ostream& os) const {
00108     os << "  ";
00109     for (int i = 0; i<n*n*n*n; i++) {
00110       if (x[i].assigned()) {
00111         if (x[i].val()<10)
00112           os << x[i] << " ";
00113         else
00114           os << (char)(x[i].val()+'A'-10) << " ";
00115       }
00116       else
00117         os << ". ";
00118       if((i+1)%(n*n) == 0)
00119         os << std::endl << "  ";
00120     }
00121     os << std::endl;
00122   }
00123 
00124 };
00125 
00129 int
00130 main(int argc, char* argv[]) {
00131   SizeOptions opt("Sudoku");
00132   opt.size(0);
00133   opt.ipl(IPL_DOM);
00134   opt.solutions(1);
00135   opt.parse(argc,argv);
00136   if (opt.size() >= n_examples) {
00137     std::cerr << "Error: size must be between 0 and "
00138               << n_examples-1 << std::endl;
00139     return 1;
00140   }
00141   Script::run<Sudoku,DFS,SizeOptions>(opt);
00142   return 0;
00143 }
00144 
00145 // STATISTICS: example-any