/// Specification to be used

const int* spec;

/// Number of filled squares

const int n_filled;

/// Size of magic square

const int n;

/// Fields of square

IntVarArray x;

/// Branching to use for model

enum {

BRANCH_SIZE, ///< Branch by size

BRANCH_AFC_SIZE, ///< Branch by size over AFC

BRANCH_CBS_MAX_SD ///< Use maximum solution density

};

/// Post constraints

MagicSquare(const SizeOptions& opt)

: Script(opt), spec(specs[opt.size()]),

n_filled(spec[1]), n(spec[0]), x(*this,n*n,1,n*n) {

// Number of fields on square

const int nn = n*n;

// Sum of all a row, column, or diagonal

const int s = nn*(nn+1) / (2*n);

// Matrix-wrapper for the square

Matrix<IntVarArray> m(x, n, n);

for (int i=0; i<n_filled; i++) {

int row, col, num;

{

int idx = 3 * i + 2;

row = spec[idx] - 1;

col = spec[idx + 1] - 1;

num = spec[idx + 2];

}

rel(*this, m(col,row), IRT_EQ, num);

}

for (int i = n; i--; ) {

linear(*this, m.row(i), IRT_EQ, s, opt.ipl());

linear(*this, m.col(i), IRT_EQ, s, opt.ipl());

}

// Both diagonals must have sum s

{

IntVarArgs d1y(n);

IntVarArgs d2y(n);

for (int i = n; i--; ) {

d1y[i] = m(i,i);

d2y[i] = m(n-i-1,i);

}

linear(*this, d1y, IRT_EQ, s, opt.ipl());

linear(*this, d2y, IRT_EQ, s, opt.ipl());

}

// All fields must be distinct

distinct(*this, x, opt.ipl());

switch (opt.branching()) {

case BRANCH_CBS_MAX_SD:

#ifdef GECODE_HAS_CBS

cbsbranch(*this, x);

#endif

case BRANCH_SIZE:

branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_SPLIT_MIN());

break;

case BRANCH_AFC_SIZE:

branch(*this, x, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_SPLIT_MIN());

break;

}

}

/// Constructor for cloning \a s

MagicSquare(MagicSquare& s)

: Script(s), spec(s.spec), n_filled(s.n_filled), n(s.n) {

x.update(*this, s.x);

}

/// Copy during cloning

virtual Space*

copy(void) {

return new MagicSquare(*this);

}

/// Print solution

virtual void

print(std::ostream& os) const {

// Matrix-wrapper for the square

Matrix<IntVarArray> m(x, n, n);

for (int i = 0; i<n; i++) {

os << "\t";

for (int j = 0; j<n; j++) {

os.width(2);

os << m(i,j) << " ";

}

os << std::endl;

}

}

SizeOptions opt("MagicSquare");

opt.iterations(1);

opt.size(0);

opt.branching(MagicSquare::BRANCH_SIZE);

opt.branching(MagicSquare::BRANCH_SIZE, "size");

opt.branching(MagicSquare::BRANCH_AFC_SIZE, "afc-size");

#ifdef GECODE_HAS_CBS

opt.branching(MagicSquare::BRANCH_CBS_MAX_SD, "maxSD");

#endif

opt.parse(argc,argv);

Script::run<MagicSquare,DFS,SizeOptions>(opt);

return 0;