main page modules namespaces classes files
Gecode home

search for 

knights.cc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2001
 *
 *  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"

class Knights : public Example {
private:
  const int n;
  IntVarArray jump;
public:

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

  Knights(const Options& opt)
    : n(opt.size), jump(this,n*n,0,n*n-1) {
    const int nn = n*n;

    // Map knight to its predecessor of succesor on board
    IntVarArgs pred(nn);
    IntVarArgs succ(nn);
    for (int i = nn; i--; ) {
      IntVar p(this,0,nn-1);
      IntVar s(this,0,nn-1);
      pred[i]=p; succ[i]=s;
    }

    // Place the first two knights
    rel(this, jump[field(0,0)], IRT_EQ, 0);
    rel(this, jump[field(1,2)], IRT_EQ, 1);

    distinct(this, jump, opt.icl);

    for (int f = 0; f < nn; f++) {
      int i = f / n;
      int j = f % n;
      // Compute array of neighbours
      int nbs[8];
      int n_nbs = 0;

      static const int moves[8][2] = {
        {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}
      };

      for (int nij = 0; nij<8 ; nij++) {
        int id = i + moves[nij][0];
        int jd = j + moves[nij][1];
        
        if ((id >= 0) && (jd >= 0) && (id < n) && (jd < n)) {
          int g = field(id,jd);
          nbs[n_nbs++] = g;
        
          BoolVar b(this,0,1);

          rel(this, succ[f], IRT_EQ, g, b);
          rel(this, pred[g], IRT_EQ, f, b);

          bool_xor(this,
                   post(this, ~(jump[g]-jump[f] == 1)),
                   post(this, ~(jump[g]-jump[f] == 1-nn)),
                   b);
        }
      }
        
      IntSet ds(nbs, n_nbs);
      dom(this, pred[f], ds);
      dom(this, succ[f], ds);
      rel(this, succ[f], IRT_NQ, pred[f]);
    }
    branch(this, succ, BVAR_NONE, BVAL_MIN);
  }

  Knights(bool share, Knights& s) : Example(share,s), n(s.n) {
    jump.update(this, share, s.jump);
  }
  virtual Space*
  copy(bool share) {
    return new Knights(share,*this);
  }
  virtual void
  print(void) {
    std::cout << "\t";
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        std::cout.width(3);
        std::cout << jump[field(i,j)] << " ";
      }
      std::cout << std::endl << "\t";
    }
    std::cout << std::endl;
  }
};

int
main(int argc, char** argv) {
  Options opt("Knights");
  opt.iterations = 100;
  opt.size       = 8;
  opt.parse(argc,argv);
  Example::run<Knights,DFS>(opt);
  return 0;
}

// STATISTICS: example-any