main page modules namespaces classes files
Gecode home

search for 

crowded-chess.cc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2001
 *     Mikael Lagerkvist, 2005
 *
 *  Last modified:
 *     $Date: 2006-08-04 16:06:52 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3517 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

#include "examples/support.hh"
#include "gecode/minimodel.hh"

const int kval[] = {
  0,   0,  0,  0,  5,
  9,  15, 21, 29, 37,
  47, 57, 69, 81, 94,
  109
};
const int nkval = 16;

class CrowdedChess : public Example {
protected:
  const int n;          
  IntVarArray s;        
  IntVarArray queens,   
    rooks;              
  BoolVarArray knights; 

  enum
    {Q,   
     R,   
     B,   
     K,   
     E,   
     PMAX 
    } piece;

  // Is (i,j) a valid position on the board?
  bool valid_pos(int i, int j) {
    return (i >= 0 && i < n) &&
      (j >= 0 && j < n);
  }

  void knight_constraints() {
    static const int kmoves[4][2] = {
      {-1,2}, {1,2}, {2,-1}, {2,1}
    };
    MiniModel::Matrix<BoolVarArray> kb(knights, n, n);
    for (int x = n; x--; )
      for (int y = n; y--; )
        for (int i = 4; i--; )
          if (valid_pos(x+kmoves[i][0], y+kmoves[i][1])) {
            IntVarArgs places(2);
            places[0] = kb(x, y);
            places[1] = kb(x+kmoves[i][0], y+kmoves[i][1]);
            linear(this, places, IRT_LQ, 1);
          }
  }


public:
  CrowdedChess(const Options& o)
    : n(o.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 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));

    MiniModel::Matrix<IntVarArray> m(s, n);

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

    count(this, s, E, IRT_EQ, e, o.icl);
    count(this, s, Q, IRT_EQ, q, o.icl);
    count(this, s, R, IRT_EQ, r, o.icl);
    count(this, s, B, IRT_EQ, b, o.icl);
    count(this, s, K, IRT_EQ, k, o.icl);

    // Integer variables for use with the element constraint
    IntVar queen(this, Q, Q), rook(this, R, R);

    // 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, o.icl);
      count(this, bb, Q, IRT_EQ, 1, o.icl);
      count(this, aa, R, IRT_EQ, 1, o.icl);
      count(this, bb, R, IRT_EQ, 1, o.icl);

      //Connect (queens|rooks)[i] to the row it is in
      element(this, aa, queens[i], queen, ICL_DOM);
      element(this, aa,  rooks[i],  rook, ICL_DOM);
    }

    // N-queens constraints
    distinct(this, queens, ICL_DOM);
    IntArgs koff(n);
    for (int i = n; i--; ) koff[i] = i;
    distinct(this, koff, queens, ICL_DOM);
    for (int i = n; i--; ) koff[i] = -i;
    distinct(this, koff, queens, ICL_DOM);

    // N-rooks constraints
    distinct(this,  rooks, ICL_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);
      }

      count(this, d1, Q, IRT_LQ, 1, o.icl);
      count(this, d2, Q, IRT_LQ, 1, o.icl);
      count(this, d3, Q, IRT_LQ, 1, o.icl);
      count(this, d4, Q, IRT_LQ, 1, o.icl);
      count(this, d1, B, IRT_LQ, 1, o.icl);
      count(this, d2, B, IRT_LQ, 1, o.icl);
      count(this, d3, B, IRT_LQ, 1, o.icl);
      count(this, d4, B, IRT_LQ, 1, o.icl);
    }

    // Handle knigths
    //Connect knigths to board
    for(int i = n*n; i--; )
      knights[i] = post(this, ~(s[i] == K));
    knight_constraints();


    // ***********************
    // Redundant constraints
    // ***********************

    // Queens and rooks not in the same place
    // Faster than going through the channeled board-connection
    for (int i = n; i--; ) {
      rel(this, queens[i], IRT_NQ, rooks[i]);
    }

    // Place bishops in two corners (from Schimpf and Hansens solution)
    // Avoids some symmetries of the problem
    rel(this, m(n-1,   0), IRT_EQ, B);
    rel(this, m(n-1, n-1), IRT_EQ, B);


    // ***********************
    // Branchings
    // ***********************
    //Place each piece in turn
    branch(this, s, BVAR_MIN_MIN, BVAL_MIN);
  }

  CrowdedChess(bool share, CrowdedChess& e)
    : Example(share,e), n(e.n) {
    s.update(this, share, e.s);
    queens.update(this, share, e.queens);
    rooks.update(this, share, e.rooks);
    knights.update(this, share, e.knights);
  }

  virtual Space*
  copy(bool share) {
    return new CrowdedChess(share,*this);
  }

  virtual void
  print(void) {
    MiniModel::Matrix<IntVarArray> m(s, n);
    char *names = static_cast<char*>(Memory::malloc(PMAX));
    const char *sep   = n < 8 ? "\t\t" : "\t";
    names[E] = '.'; names[Q] = 'Q'; names[R] = 'R';
    names[B] = 'B'; names[K] = 'K';

    for (int r = 0; r < n; ++r){
      // Print main board
      std::cout << '\t';
      for (int c = 0; c < n; ++c) {
        std::cout << names[m(r, c).val()];
      }
      // Print each piece on its own
      for (int p = 0; p < PMAX; ++p) {
        if (p == E) continue;
        std::cout << sep;
        for (int c = 0; c < n; ++c) {
          if (m(r, c).val() == p) std::cout << names[p];
          else                   std::cout << names[E];
        }
      }
      std::cout << std::endl;
    }
    std::cout << std::endl;
  }
};

int
main(int argc, char** argv) {
  Options o("CrowdedChess");
  o.icl        = ICL_DOM;
  o.size       = 7;
  o.parse(argc,argv);
  if(o.size < 5) {
    std::cerr << "Error: Size must be at least 5" << std::endl;
    return 1;
  }
  Example::run<CrowdedChess,DFS>(o);
  return 0;
}

// STATISTICS: example-any