queen-armies.cc

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Mikael Lagerkvist, 2006
 *
 *  Last modified:
 *     $Date: 2008-02-05 10:57:39 +0100 (Tue, 05 Feb 2008) $ by $Author: zayenz $
 *     $Revision: 6053 $
 *
 *  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 "examples/support.hh"
#include "gecode/set.hh"
#include "gecode/minimodel.hh"


IntSet *A;

class QueenArmies : public Example {
public:
  const int n;
  SetVar U, 
    W; 
  BoolVarArray w, 
    b; 
  IntVar q; 

  enum {
    BRANCH_NAIVE,   
    BRANCH_SPECIFIC 
  };
  QueenArmies(const SizeOptions& opt) :
    n(opt.size()),
    U(this, IntSet::empty, IntSet(0, n*n)),
    W(this, IntSet::empty, IntSet(0, n*n)),
    w(this, n*n, 0, 1),
    b(this, n*n, 0, 1),
    q(this, 0, n*n)
  {
    // Basic rules of the model
    for (int i = n*n; i--; ) {
      // w[i] means that no blacks are allowed on A[i]
      dom(this, U, SRT_DISJ, A[i], w[i]);
      // Make sure blacks and whites are disjoint.
      post(this, tt(!w[i] || !b[i]));
      // If i in U, then b[i] has a piece.
      dom(this, U, SRT_SUP, i, b[i]);
    }

    // Connect optimization variable to number of pieces
    linear(this, w, IRT_EQ, q);
    linear(this, b, IRT_GQ, q);

    // Connect cardinality of U to the number of black pieces.
    IntVar unknowns(this, 0, n*n);
    cardinality(this, U, unknowns);
    post(this, q <= unknowns);
    linear(this, b, IRT_EQ, unknowns);

    if (opt.branching() == BRANCH_NAIVE) {
      branch(this, w, INT_VAR_NONE, INT_VAL_MAX);
      branch(this, b, INT_VAR_NONE, INT_VAL_MAX);
    } else {
      QueenBranch::post(this);
      assign(this, b, INT_ASSIGN_MAX);
    }
  }
  QueenArmies(bool share, QueenArmies& s)
    : Example(share,s), n(s.n)
  {
    U.update(this, share, s.U);
    W.update(this, share, s.W);
    w.update(this, share, s.w);
    b.update(this, share, s.b);
    q.update(this, share, s.q);
  }

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

  void
  constrain(Space* s) {
    rel(this, q, IRT_GR, static_cast<QueenArmies*>(s)->q.val());
  }


  virtual void
  print(std::ostream& os) {
    os << '\t';
    for (int i = 0; i < n*n; ++i) {
      if (w[i].assigned() && w[i].val()) os << "W";
      else if (b[i].assigned() && b[i].val()) os << "B";
      else if (!w[i].assigned() && !b[i].assigned()) os << " ";
      else os << ".";
      if ((i+1)%n == 0) os << std::endl << (i!=(n*n-1)?"\t":"");
    }
    os << "Number of white queens: " << q << std::endl << std::endl;
  }

  class QueenBranch : Branching {
    mutable int pos;
    // Construct branching
    QueenBranch(Space* home)
      : Branching(home), pos(-1) {}
    // Constructor for cloning
    QueenBranch(Space* home, bool share, QueenBranch& b)
      : Branching(home, share, b), pos(b.pos) {}

  public:
    virtual bool status(const Space* home) const {
      const QueenArmies *q = static_cast<const QueenArmies*>(home);
      int maxsize = -1;
      pos = -1;

      for (int i = q->n*q->n; i--; ) {
        if (q->w[i].assigned()) continue;
        IntSetRanges ai(A[i]);
        SetVarUnknownRanges qU(q->U);
        Iter::Ranges::Inter<IntSetRanges, SetVarUnknownRanges> r(ai, qU);
        int size = Iter::Ranges::size(r);
        if (size > maxsize) {
          maxsize = size;
          pos = i;
        }
      }
      if (pos == -1) return false;
      return true;
    }
    virtual BranchingDesc* description(const Space*) const {
      assert(pos != -1);
      return new PosValDesc<bool,2>(this, pos, true);
    }
    virtual ExecStatus commit(Space* home, const BranchingDesc* d, 
                              unsigned int a) {
      QueenArmies *q = static_cast<QueenArmies*>(home);
      const PosValDesc<bool,2> *pvd = static_cast<const PosValDesc<bool,2>*>(d);
      bool val = a == 0 ? pvd->val() : !pvd->val();
      return me_failed(Int::BoolView(q->w[pvd->pos()]).eq(q, val))
        ? ES_FAILED
        : ES_OK;
    }
    virtual Actor* copy(Space *home, bool share) {
      return new (home) QueenBranch(home, share, *this);
    }
    virtual const char* name(void) const {
      return "QueenBranching";
    }

    static void post(QueenArmies* home) {
      (void) new (home) QueenBranch(home);
    }
  };
};

int pos(int i, int j, int n) {
  return i*n + j;
}

int
main(int argc, char* argv[]) {
  SizeOptions opt("QueenArmies");
  opt.size(6);
  opt.branching(QueenArmies::BRANCH_SPECIFIC);
  opt.branching(QueenArmies::BRANCH_NAIVE, "naive");
  opt.branching(QueenArmies::BRANCH_SPECIFIC, "specific");
  opt.solutions(0);
  opt.parse(argc,argv);

  // Set up the A-sets
  // A[i] will contain the values attacked by a queen at position i
  int n = opt.size();
  A = new IntSet[n*n];
  int *p = new int[std::max(n*n, 25)];
  int pn = 0;
  for (int i = n; i--; ) {
    for (int j = n; j--; ) {
      int dir[][2] = {
        { 0,  1},
        { 1,  1},
        { 1,  0},
        { 0, -1},
        {-1, -1},
        {-1,  0},
        { 1, -1},
        {-1,  1}
      };
      p[pn++] = pos(i, j, n);
      for (int k = 8; k--; ) {
        for (int l = 0; l < n
               && 0 <= (i+l*dir[k][0]) && (i+l*dir[k][0]) < n
               && 0 <= (j+l*dir[k][1]) && (j+l*dir[k][1]) < n; ++l) {
          p[pn++] = pos(i+l*dir[k][0], j+l*dir[k][1], n);
        }
      }

      A[pos(i, j, n)] = IntSet(p, pn);

      pn = 0;
    }
  }
  delete [] p;

  Example::run<QueenArmies,BAB,SizeOptions>(opt);
  return 0;
}

// STATISTICS: example-any