00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041
00042 using namespace Gecode;
00043
00054 class MagicSquare : public Script {
00055 private:
00057 const int n;
00059 IntVarArray x;
00060
00061 public:
00063 enum {
00064 BRANCH_SIZE,
00065 BRANCH_AFC_SIZE
00066 };
00068 MagicSquare(const SizeOptions& opt)
00069 : Script(opt), n(opt.size()), x(*this,n*n,1,n*n) {
00070
00071 const int nn = n*n;
00072
00073
00074 const int s = nn*(nn+1) / (2*n);
00075
00076
00077 Matrix<IntVarArray> m(x, n, n);
00078
00079 for (int i = n; i--; ) {
00080 linear(*this, m.row(i), IRT_EQ, s, opt.ipl());
00081 linear(*this, m.col(i), IRT_EQ, s, opt.ipl());
00082 }
00083
00084 {
00085 IntVarArgs d1y(n);
00086 IntVarArgs d2y(n);
00087 for (int i = n; i--; ) {
00088 d1y[i] = m(i,i);
00089 d2y[i] = m(n-i-1,i);
00090 }
00091 linear(*this, d1y, IRT_EQ, s, opt.ipl());
00092 linear(*this, d2y, IRT_EQ, s, opt.ipl());
00093 }
00094
00095
00096 distinct(*this, x, opt.ipl());
00097
00098
00099 rel(*this, m(0,0), IRT_GR, m(0,n-1));
00100 rel(*this, m(0,0), IRT_GR, m(n-1,0));
00101
00102 switch (opt.branching()) {
00103 case BRANCH_SIZE:
00104 branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_SPLIT_MIN());
00105 break;
00106 case BRANCH_AFC_SIZE:
00107 branch(*this, x, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_SPLIT_MIN());
00108 break;
00109 }
00110 }
00111
00113 MagicSquare(bool share, MagicSquare& s) : Script(share,s), n(s.n) {
00114 x.update(*this, share, s.x);
00115 }
00116
00118 virtual Space*
00119 copy(bool share) {
00120 return new MagicSquare(share,*this);
00121 }
00123 virtual void
00124 print(std::ostream& os) const {
00125
00126 Matrix<IntVarArray> m(x, n, n);
00127 for (int i = 0; i<n; i++) {
00128 os << "\t";
00129 for (int j = 0; j<n; j++) {
00130 os.width(2);
00131 os << m(i,j) << " ";
00132 }
00133 os << std::endl;
00134 }
00135 }
00136
00137 };
00138
00142 int
00143 main(int argc, char* argv[]) {
00144 SizeOptions opt("MagicSquare");
00145 opt.iterations(1);
00146 opt.size(7);
00147 opt.branching(MagicSquare::BRANCH_SIZE);
00148 opt.branching(MagicSquare::BRANCH_SIZE, "size");
00149 opt.branching(MagicSquare::BRANCH_AFC_SIZE, "afc-size");
00150 opt.parse(argc,argv);
00151 Script::run<MagicSquare,DFS,SizeOptions>(opt);
00152 return 0;
00153 }
00154
00155
00156