Generated on Fri Oct 19 11:24:48 2018 for Gecode by doxygen 1.6.3

magic-square.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  *  Copyright:
00007  *     Christian Schulte, 2001
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/driver.hh>
00035 #include <gecode/int.hh>
00036 #include <gecode/minimodel.hh>
00037 
00038 using namespace Gecode;
00039 
00050 class MagicSquare : public Script {
00051 private:
00053   const int n;
00055   IntVarArray x;
00056 
00057 public:
00059   enum {
00060     BRANCH_SIZE,    
00061     BRANCH_AFC_SIZE 
00062   };
00064   MagicSquare(const SizeOptions& opt)
00065     : Script(opt), n(opt.size()), x(*this,n*n,1,n*n) {
00066     // Number of fields on square
00067     const int nn = n*n;
00068 
00069     // Sum of all a row, column, or diagonal
00070     const int s  = nn*(nn+1) / (2*n);
00071 
00072     // Matrix-wrapper for the square
00073     Matrix<IntVarArray> m(x, n, n);
00074 
00075     for (int i = n; i--; ) {
00076       linear(*this, m.row(i), IRT_EQ, s, opt.ipl());
00077       linear(*this, m.col(i), IRT_EQ, s, opt.ipl());
00078     }
00079     // Both diagonals must have sum s
00080     {
00081       IntVarArgs d1y(n);
00082       IntVarArgs d2y(n);
00083       for (int i = n; i--; ) {
00084         d1y[i] = m(i,i);
00085         d2y[i] = m(n-i-1,i);
00086       }
00087       linear(*this, d1y, IRT_EQ, s, opt.ipl());
00088       linear(*this, d2y, IRT_EQ, s, opt.ipl());
00089     }
00090 
00091     // All fields must be distinct
00092     distinct(*this, x, opt.ipl());
00093 
00094     // Break some (few) symmetries
00095     rel(*this, m(0,0), IRT_GR, m(0,n-1));
00096     rel(*this, m(0,0), IRT_GR, m(n-1,0));
00097 
00098     switch (opt.branching()) {
00099     case BRANCH_SIZE:
00100       branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_SPLIT_MIN());
00101       break;
00102     case BRANCH_AFC_SIZE:
00103       branch(*this, x, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_SPLIT_MIN());
00104       break;
00105     }
00106   }
00107 
00109   MagicSquare(MagicSquare& s) : Script(s), n(s.n) {
00110     x.update(*this, s.x);
00111   }
00112 
00114   virtual Space*
00115   copy(void) {
00116     return new MagicSquare(*this);
00117   }
00119   virtual void
00120   print(std::ostream& os) const {
00121     // Matrix-wrapper for the square
00122     Matrix<IntVarArray> m(x, n, n);
00123     for (int i = 0; i<n; i++) {
00124       os << "\t";
00125       for (int j = 0; j<n; j++) {
00126         os.width(2);
00127         os << m(i,j) << "  ";
00128       }
00129       os << std::endl;
00130     }
00131   }
00132 
00133 };
00134 
00138 int
00139 main(int argc, char* argv[]) {
00140   SizeOptions opt("MagicSquare");
00141   opt.iterations(1);
00142   opt.size(7);
00143   opt.branching(MagicSquare::BRANCH_SIZE);
00144   opt.branching(MagicSquare::BRANCH_SIZE, "size");
00145   opt.branching(MagicSquare::BRANCH_AFC_SIZE, "afc-size");
00146   opt.parse(argc,argv);
00147   Script::run<MagicSquare,DFS,SizeOptions>(opt);
00148   return 0;
00149 }
00150 
00151 // STATISTICS: example-any
00152