Method CrowdedChess

examples/crowded-chess.cpp:236–340

The model of the problem

  /// The model of the problem
  CrowdedChess(const SizeOptions& opt)
    : Script(opt),
      n(opt.size()),
      s(*this, n*n, 0, PMAX-1),
      queens(*this, n, 0, n-1),
      rooks(*this, n, 0, n-1),
      knights(*this, n*n, 0, 1) {
    const int nkval = sizeof(kval)/sizeof(int);
    const int nn = n*n, q = n, r = n, b = (2*n)-2,
      k = n <= nkval ? kval[n-1] : kval[nkval-1];
    const int e = nn - (q + r + b + k);

    assert(nn == (e + q + r + b + k));

    Matrix<IntVarArray> m(s, n);

    // ***********************
    // Basic model
    // ***********************

    count(*this, s, E, IRT_EQ, e, opt.ipl());
    count(*this, s, Q, IRT_EQ, q, opt.ipl());
    count(*this, s, R, IRT_EQ, r, opt.ipl());
    count(*this, s, B, IRT_EQ, b, opt.ipl());
    count(*this, s, K, IRT_EQ, k, opt.ipl());

    // Collect rows and columns for handling rooks and queens
    for (int i = 0; i < n; ++i) {
      IntVarArgs aa = m.row(i), bb = m.col(i);

      count(*this, aa, Q, IRT_EQ, 1, opt.ipl());
      count(*this, bb, Q, IRT_EQ, 1, opt.ipl());
      count(*this, aa, R, IRT_EQ, 1, opt.ipl());
      count(*this, bb, R, IRT_EQ, 1, opt.ipl());

      // Connect (queens|rooks)[i] to the row it is in
      element(*this, aa, queens[i], Q, IPL_DOM);
      element(*this, aa,  rooks[i], R, IPL_DOM);
    }

    // N-queens constraints
    distinct(*this, queens, IPL_DOM);
    distinct(*this, IntArgs::create(n,0,1), queens, IPL_DOM);
    distinct(*this, IntArgs::create(n,0,-1), queens, IPL_DOM);

    // N-rooks constraints
    distinct(*this,  rooks, IPL_DOM);

    // Collect diagonals for handling queens and bishops
    for (int l = n; l--; ) {
      const int il = (n-1) - l;
      IntVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
      for (int i = 0; i <= l; ++i) {
        d1[i] = m(i+il, i);
        d2[i] = m(i, i+il);
        d3[i] = m((n-1)-i-il, i);
        d4[i] = m((n-1)-i, i+il);
      }