crowded-chess.cpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2001
 *     Mikael Lagerkvist, 2005
 *
 *  Last modified:
 *     $Date: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $
 *     $Revision: 11473 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>

using namespace Gecode;

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

namespace {
  TupleSet bishops;
  class Bishops : public Space {
  public:
    const int n;
    BoolVarArray k;
    bool valid_pos(int i, int j) {
      return (i >= 0 && i < n) && (j >= 0 && j < n);
    }
    Bishops(int size)
      : n(size), k(*this,n*n,0,1) {
      Matrix<BoolVarArray> kb(k, n, n);
      for (int l = n; l--; ) {
        const int il = (n-1) - l;
        BoolVarArgs d1(l+1), d2(l+1), d3(l+1), d4(l+1);
        for (int i = 0; i <= l; ++i) {
          d1[i] = kb(i+il, i);
          d2[i] = kb(i, i+il);
          d3[i] = kb((n-1)-i-il, i);
          d4[i] = kb((n-1)-i, i+il);
        }

        linear(*this, d1, IRT_LQ, 1);
        linear(*this, d2, IRT_LQ, 1);
        linear(*this, d3, IRT_LQ, 1);
        linear(*this, d4, IRT_LQ, 1);
      }

      linear(*this, k, IRT_EQ, 2*n - 2);
      // Forced bishop placement from crowded chess model
      rel(*this, kb(n-1,   0), IRT_EQ, 1);
      rel(*this, kb(n-1, n-1), IRT_EQ, 1);
      branch(*this, k,
             tiebreak(INT_VAR_DEGREE_MAX,INT_VAR_SIZE_MIN), INT_VAL_MAX);
    }
    Bishops(bool share, Bishops& s) : Space(share,s), n(s.n) {
      k.update(*this, share, s.k);
    }
    virtual Space* copy(bool share) {
      return new Bishops(share,*this);
    }
  };
  void init_bishops(int size) {
    Bishops* prob = new Bishops(size);
    DFS<Bishops> e(prob); IntArgs ia(size*size);
    delete prob;

    while (Bishops* s = e.next()) {
      for (int i = size*size; i--; )
        ia[i] = s->k[i].val();
      bishops.add(ia);
      delete s;
    }

    bishops.finalize();
  }
}
class CrowdedChess : public Script {
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(void) {
    static const int kmoves[4][2] = {
      {-1,2}, {1,2}, {2,-1}, {2,1}
    };
    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]))
            rel(*this,
                kb(x, y),
                BOT_AND,
                kb(x+kmoves[i][0], y+kmoves[i][1]),
                0);
  }


public:
  enum {
    PROP_TUPLE_SET, 
    PROP_DECOMPOSE  
  };

  CrowdedChess(const SizeOptions& 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.icl());
    count(*this, s, Q, IRT_EQ, q, opt.icl());
    count(*this, s, R, IRT_EQ, r, opt.icl());
    count(*this, s, B, IRT_EQ, b, opt.icl());
    count(*this, s, K, IRT_EQ, k, opt.icl());

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

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

    // N-queens constraints
    distinct(*this, queens, ICL_DOM);
    distinct(*this, IntArgs::create(n,0,1), queens, ICL_DOM);
    distinct(*this, IntArgs::create(n,0,-1), 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, opt.icl());
      count(*this, d2, Q, IRT_LQ, 1, opt.icl());
      count(*this, d3, Q, IRT_LQ, 1, opt.icl());
      count(*this, d4, Q, IRT_LQ, 1, opt.icl());
      if (opt.propagation() == PROP_DECOMPOSE) {
        count(*this, d1, B, IRT_LQ, 1, opt.icl());
        count(*this, d2, B, IRT_LQ, 1, opt.icl());
        count(*this, d3, B, IRT_LQ, 1, opt.icl());
        count(*this, d4, B, IRT_LQ, 1, opt.icl());
      }
    }
    if (opt.propagation() == PROP_TUPLE_SET) {
      IntVarArgs b(s.size());
      for (int i = s.size(); i--; )
        b[i] = channel(*this, expr(*this, (s[i] == B)));
      extensional(*this, b, bishops, EPK_DEF, opt.icl());
    }

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


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

    // Queens and rooks not in the same place
    // Faster than going through the channelled 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);


    // ***********************
    // Branching
    // ***********************
    // Place each piece in turn
    branch(*this, s, INT_VAR_MIN_MIN, INT_VAL_MIN);
  }

  CrowdedChess(bool share, CrowdedChess& e)
    : Script(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(std::ostream& os) const {
    Matrix<IntVarArray> m(s, n);
    char names[PMAX];
    names[E] = '.'; names[Q] = 'Q'; names[R] = 'R';
    names[B] = 'B'; names[K] = 'K';
    const char* sep   = n < 8 ? "\t\t" : "\t";

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

int
main(int argc, char* argv[]) {
  SizeOptions opt("CrowdedChess");
  opt.propagation(CrowdedChess::PROP_TUPLE_SET);
  opt.propagation(CrowdedChess::PROP_TUPLE_SET,
                  "extensional",
                  "Use extensional propagation for bishops-placement");
  opt.propagation(CrowdedChess::PROP_DECOMPOSE,
                  "decompose",
                  "Use decomposed propagation for bishops-placement");
  opt.icl(ICL_DOM);
  opt.size(8);
  opt.parse(argc,argv);
  if (opt.size() < 5) {
    std::cerr << "Error: size must be at least 5" << std::endl;
    return 1;
  }
  init_bishops(opt.size());
  Script::run<CrowdedChess,DFS,SizeOptions>(opt);
  return 0;
}

// STATISTICS: example-any