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 #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
00067 const int nn = n*n;
00068
00069
00070 const int s = nn*(nn+1) / (2*n);
00071
00072
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
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
00092 distinct(*this, x, opt.ipl());
00093
00094
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
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
00152