N-Queens problem

The n-queens problem, a generalization of the 8-queens problem, consists in placing n queens on a nxn checkboard so that no queen can hit any other in one move.

To compile the n-queens sample checkout the code with

$ svn co http://code.100allora.it/svn/metslib/trunk metslib-trunk

Then

$ cd metslib-trunk/metslib
$ ./autogen.sh
$ make
$ sudo make install

You can now compile the sample using.

$ cd ../samples/n-queens/
$ ./autogen.sh
$ make

And finally start a search with

$ ./src/queens 8

or

$ ./src/queens 16

or again:

$ ./src/queens 2500

You'll be amazed by the speed of the algorithm... it was up to 10 time faster than a very similar implementation with Genetic Algorithms (using the great  GAlib) that you can find here.

Please note that this is intended as a sample code on a simple test problem. There are construtive solutions to the n-queens problem that are much faster.

Commented source code

Includes and namespaces

#include <iostream>
#include <valarray>
#include <algorithm>

#include <metslib/mets.h>     // Include the metslib main header.

using namespace std;

using namespace mets;         // the namespace for mets classes


int nmove = 0, tmove = 0;     // take trak of made moves

The problem class

// The problem is well known and has n! solutions, most of which are not correct.
// A solution is correct only if no queen can eat another queen in one move.
class queens : public mets::feasible_solution
{
  friend class queens_moves;  // queens move knows a lot about us, it must.
  friend ostream& operator<<(ostream& os, const queens& q);
  
public:
  // take a random permutation of columns (we assume every queen must be on a different
  // row and reduce the problem to the shuffling of the columns).
  explicit queens(int dim) : feasible_solution(), dim_m(dim), sol_m(), rng() { 
    vector<int> init(dim);
    for(int i=0; i < dim; i++) init[i] = i;
    random_shuffle(init.begin(), init.end(), rng); /*** \label{lst:queensstart} */
    sol_m.resize(dim); 
    for(int i=0; i < dim; i++) sol_m[i] = init[i];
  }

  // tabu search needs a copy constructor
  explicit queens(const queens& other) 
    : feasible_solution(other), dim_m(other.dim_m), sol_m(other.sol_m), rng() {
  }

  // tabu search needs to copy solutions 
  queens& operator=(const feasible_solution& other) {
    const queens& o = static_cast<const queens&>(other);
    dim_m = o.dim_m;
    sol_m = o.sol_m;
    return *this;
  }

  // swap two columns
  void swap(int a, int b) {
    int tmp = sol_m[a];
    sol_m[a] = sol_m[b];
    sol_m[b] = tmp;
  }

  // problem dimension (m x m checkboard)
  int dim() const { return dim_m; }

  // The cost function counts queens under attack.
  gol_type cost_function() const { /*** \label{lst:queenscost} */
    int cost = 0; // un int basta per problemi fino a 500 regine ed oltre
    for(int i = 0; i < dim_m - 1; i++)
      for(int j = 1; j < dim_m - i; j++) {
        if(sol_m[i+j] == sol_m[i]-j or sol_m[i+j] == sol_m[i]+j) cost++;
      }
    return cost;
  }
  
protected:
  int dim_m;
  valarray<int> sol_m;  // valarrays are as fast as C arrays, but much nicer.
  mets::random_integer rng;
};

Implementation of the solution interface:

// ostream operator to print a solution on a ostream (and cout)
ostream& operator<<(ostream& os, const queens& q) {
  for(int ii = 0; ii < q.dim_m; ++ii) {
    for(int jj=0; jj < q.sol_m[ii]; jj++)
      os << ". ";
    os << "Q ";
    for(int jj = q.sol_m[ii] + 1; jj < q.dim(); jj++)
      os << ". ";
    os << endl;
  } 
  os << endl;
  for(int ii = 0; ii < q.dim_m; ++ii) {
    os << "Q";
    if(ii >= 26) os << (char)('a'-1+(ii)/26);
    os << (char)('a'+ii%26);
    os << (q.sol_m[ii]+1);
    if(ii < q.dim_m-1) os << ", ";
  }
  os << endl;
  return os;
}

The swap move type

// Implementation of the only move type we need, the swap move.
// A move class represents a type of move and an instance of this
// class is a particular move that can be made.
class queens_swap : public mets::mana_move
{
  friend class queens_moves;

public:
  // create a swap move between column "a" with column "b"
  // this doesn't know on wich solution will be applyed, 
  // and is an abstract move.
  queens_swap(int a, int b) : a_m(a), b_m(b) { }

  // swap column "a" with column "b" on the given solution instance
  void apply(feasible_solution& s) {
    queens& q = static_cast<queens&>(s);
    q.swap(a_m, b_m);
    tmove++; nmove++;
  }

  // "un"swap column "a" with column "b" on the given solution instance
  // unapply moves can be called only right after the relative apply, so
  // if you need to you can memorize the move in apply and put it back here.
  // Anyway knowing how to do the move backwars make the whole thing a lot faster.
  void unapply(feasible_solution& s) {
    queens& q = static_cast<queens&>(s);
    q.swap(b_m, a_m);
    nmove--;
  }

  // we need to copy moves
  mets::mana_move* clone() const { return new queens_swap(a_m, b_m); }

  // an hash used by the hash map in simple_tabu_list 
  // this is an hash code for the move, it should be 
  // "fairly" unique for each different move.
  size_t hash() const { return a_m << 16 ^ b_m; }

  // comparison operator, simple_tabu_list needs this to know
  // if two moves are the same.
  bool operator==(const mana_move& o) const {
    const queens_swap& qs = static_cast<const queens_swap&>(o);
    return (a_m == qs.a_m && b_m == qs.b_m);
  }

private:
  int a_m;
  int b_m;
};

The neighborhood generator

// neighborhood generator.
class queens_moves : public mets::move_manager
{
public:  
  // make "max" moves.
  explicit queens_moves(int max) : mets::move_manager(), rng(), mm(max) { 
    for(int ii = 0; ii < mm; ++ii) moves_m.push_back(new queens_swap(0,0));
  }

  // fill all the moves with random values
  void refresh(feasible_solution& s) {
    queens& q = static_cast<queens&>(s);
    for(int ii = 0; ii < mm; ++ii) {
      int col = rng(q.dim());
      int ncol = rng(q.dim());
      while(ncol == col) ncol = rng(q.dim()); // use different values
      static_cast<queens_swap*>(moves_m[ii])->a_m = col;
      static_cast<queens_swap*>(moves_m[ii])->b_m = ncol;
    }
  }

protected:
  mets::random_integer rng;
  int mm;  
};

A progress listener

// an observer/listener on the algorithm status
// that simply prints advance status
class tobserver : public search_listener
{
public:
  tobserver() : search_listener() {}
  void update(mets::abstract_search * as) {
    if(as->step() == 0) 
      cerr << nmove << " " <<as->working().cost_function() << endl;
  }
};

An utility funcion

// print usage information
void usage() {
  clog << "usage: queens n (with n >3)" << endl;
  exit(1);
}

The main

int main(int argc, char *argv[]) {
  
  // handle command line parameter
  if(argc != 2) usage();
  int dim = atoi(argv[1]);
  if(dim<=3) usage();

  // make two new "dim" problem, one to work on and one
  // to memorize the best solution so far.
  queens working(dim);
  queens best(working);

  // do dim*2 moves every iteration
  queens_moves moves(dim*2);

  // take dim*7 moves int the tabu list
  simple_tabu_list tabus(dim/7); 

  // use the best known aspiration criteria
  best_ever_criteria beac;

  // exit only when an optimal solution is found
  threshold_termination_criteria ttc(0); 

  // initialize the search instance with working and best solutions,
  // the move manager, the tabu list, the aspiration criteria and the
  // termination criteria
  mets::tabu_search ts(working, best, moves, tabus, beac, ttc);

  // attach the observer to the algorithm
  tobserver o;
  ts.attach(o);

  // start the search process
  try {
    ts.search();
  } catch(no_moves_error) {
    cerr << "There are no non-tabu moves" << endl;
  }
  // from now on "best" contains the best solution found

  // print resultes
  cerr << endl << "Moves: " << tmove << " " << nmove << endl;
  cout << "Cost: " << best.cost_function() << endl;

  // print the best solution
  cout << best << endl;
  
  // success! :)
  return 0;
}