Getting started

Getting started: The NQueen problem

This page describes two scripts to solve the academic NQueen problem. It focuses not on the NQueen, but on the features of Asteroid.

The structure of the script is as follows:

1. Create a model
2. Create a constraint system
3. Create some variables and invariants in the model, constraints in the constraint system
4. Close the constraint system
5. add some more variables and invariants, e.g. to speed up neighbourhood exploration
6. Close the model
7. Perform the exploration: modify the value of the variable whose value is not fixed by any invariant and explore the value of the variable at the output of the propagation graph such as the degree of violation of the constraint system (= the objective function)

It is possible to create additional invariants and variable in the model after the constraint system is closed, or before it is created. This is done in Asteroid to declare some structure that efficiently manages the tabu list through invariants.

The first script is a naive implementation of the NQueen. Queens are maintained on different rows at all times by initializing model with different rows for each queens, and only considering queen swap neighbourhood. The selected neighbour is the best pair of queens to swap with respect to the violation degree of the two alldiff constraints. The script also proposes a tabu on the queens: a queen cannot be moved for 4 cycles after it has been moved. Finally, the script features a jump away function, to randomly jump to a random position if a plateau is noticed during the search.

package Constraints.Tests;
import Search._;
import Invariants.Core.ComputationStructure._;
import Constraints.Core._;
import Invariants.Core.ComputationStructure.Implicits._;
import Invariants.Library.Numeric.Implicits._;
import Constraints.Library.Global.{AllDiff};

object NQueens extends SearchEngine{
  def main(args: Array[String]) {

    //declaring some constants of the problem
    val N:Int=40;
    val min = 0;
    val max = N-1;
    val range:Range = Range(0,N);
    val tabulength = 1;
    val MaxIT = 10000;

    println("NQueens(" + N + ")");

    //here are created the model and the variables of the problem
    val m: Model = new Model(false);

    val Queens:Array[IntVar] = new Array[IntVar](N);
    for (q <- range){Queens(q) = new IntVar(m, min, max, q, "queen" + q)};

    //now, the constraint system is declared, and populated with the two alldiff constraints
    val c:ConstraintSystem = new ConstraintSystem(m);

    //c.Post(AllDiff(Queens)) handled trough permutations
    //notice that constraints are posted on variables that are derived through invariants 
    // (plus and minus are infix constructs that instantiate sum2 and minus invariants, respectively)
    c.Post(AllDiff(for ( q <- range) yield (q plus Queens(q)).ToIntVar));
    c.Post(AllDiff(for ( q <- range) yield (q minus Queens(q)).ToIntVar));

    //constraint system and model need to be closed. 
    //when a constraint system is closed, no more constraints can be posted in it. 
    c.close;
    //when the model is closed, Asteroid constructs the underlying DAG that is used to perform propagation.  
    m.close;

    var it:Int =0;

    //this memorizes the tabu of each queen
    var Tabu = (for(q <- range)yield -1).toArray;

    var longueurplateau = 0;
    while((c.Violation.GetValue() > 0) && (it.GetValue() < MaxIT)){
      val oldviolation:Int = c.Violation;
      val allowedqueens = range.filter(q => Tabu(q) < it);
      val Q1AndQ2:(Int,Int) = SelectMin2(allowedqueens,
                                         allowedqueens, 
                                         (q1:Int, q2:Int) => c.GetSwapViol(Queens(q1),Queens(q2)), 
                                         (q1:Int,q2:Int) => q1 != q2);
      val q1 = Q1AndQ2._1;
      val q2 = Q1AndQ2._2;

      //this performs the move by swapping the two queens, and updates the tabu array
      Queens(q1) :=: Queens(q2);
      Tabu(q1) = it + tabulength;
      Tabu(q2) = it + tabulength;

      it += 1;
      println("it: " + it + " " + c.Violation + " (swapped "+ q1 + " and " + q2 + ")");
      if(oldviolation <= c.Violation.GetValue()) longueurplateau+=1 else longueurplateau = 0

      if (longueurplateau > 5){
        println("jump away");
        for (i <- 1 to N/5){
          Queens(SelectFrom(range)) :=: Queens(SelectFrom(range));
        }
        longueurplateau = 0;
      }
    }
    println(c.Violation);
    println(m.GetSolution(true));
  }
}

The second script is a more advanced version of the NQueen. It is basically identical to the previous except that it incrementally maintains the set of the most violated non tabu queens through dedicated invariants. This set is used to select the first queen to involve in the swap. The second queen is selected as the non tabu queen such that the swap is the best one. The non tabu queen is selected from a set that is maintained incrementally as well.

On this script, you can see an important feature of asteroid: any variable can have an associated degree of violation; they just need to be registered to the constraint system before it is closed. Once it is closed, their associated violation can be queried, and used in any invariants, as they are IntVar. The invariants for maintaining the most violated non tabu queen are declared after the constraint system is closed, and before the model is closed. Notice that the number of iteration must be an IntVar as well. It is an input of the SelectLESetQueue invariant. This invariant is dedicated for the management of tabu sets. It only allows a limited set of updates to the values of its input variables (see scaladoc).

package Constraints.Tests;
import Search._;
import Invariants.Core.ComputationStructure._;
import Constraints.Core._;
import Invariants.Core.ComputationStructure.Implicits._;
import Invariants.Library.Numeric.Implicits._;
import Invariants.Library.Logic._;
import Invariants.Library.MinMax._;
import Constraints.Library.Global._;

object NQueens3 extends SearchEngine with stopwatch{
  def main(args: Array[String]) {

    startWatch();

    val N:Int=20;

    val min = 0;
    val max = N-1;
    val range:Range = Range(0,N);
    val tabulength = 2;
    val MaxIT = 10000;

    println("NQueens(" + N + ")");

    val m: Model = new Model(false,true,true);

    //notice that here, the queens are initialized with a random permutation. 
    //the random permutation feature is provided by the SearchEngine trait

    val it:Iterator[Int] = GetRandomPermutation(N);
    val Queens:Array[IntVar] = (for (q <- range) yield new IntVar(m, min, max, it.next, "queen" + q)).toArray;

    val c:ConstraintSystem = new ConstraintSystem(m);

    //c.Post(AllDiff(Queens)) //enforced because we swap queens and they are always alldiff
    c.Post(AllDiff(for ( q <- range) yield (q plus Queens(q)).ToIntVar));
    c.Post(AllDiff(for ( q <- range) yield (q minus Queens(q)).ToIntVar));

    //The constraint system is notified here that it must maintain a global degree of violation for each queen. 
    //if omitted, the degree of violation will not take into account the constraints 
    //where the variable is indirectly involved via one or more invariant
    for (q <- range){c.RegisterForViolation(Queens(q))};

    c.close;

    //after closing the constraint system, we can access to the global violation associated to the variables
    val ViolationArray:Array[IntVar] = (for(q <- range) yield c.GetViolation(Queens(q))).toArray;

    //we are defining a set of incremental invariants to incrementally maintain the set of the non tabu most violated queens
    //as such, we need to store tabu and iteration number into IntVar, so that they are handled by the model
    val Tabu:Array[IntVar] = (for (q <- range) yield new IntVar(m, 0, Int.MaxValue, 0, "Tabu_queen" + q)).toArray;
    val It = new IntVar(m,0,Int.MaxValue,0,"it");

    //This invariant is specifically intended for taby. Notice that it relies on a set and a queue. 
    //As such, not all updates are tolerated, see the doc of this invariants for more info. 
    val NonTabuQueens:IntSetVar = SelectLESetQueue(Tabu, It);

    val NonTabuMaxViolQueens:IntSetVar = ArgMaxArray(ViolationArray, NonTabuQueens);

    m.close;

    println("run time after model close: "+ getWatchString());

    var longueurplateau = 0;
    var minviolationplateau = c.Violation.GetValue();
    while((c.Violation.GetValue() > 0) && (It.GetValue() < MaxIT)){
      //this randomly selects the first queen from our incrementally handled set of queens
      val q1 = SelectFrom(NonTabuMaxViolQueens);

      //the second queen is selected as well from an incrementally defined set
      val q2 = SelectMin(NonTabuQueens, (q:Int) => c.GetSwapViol(Queens(q1),Queens(q)), (q:Int) => q!=q1);

      Queens(q1) :=: Queens(q2);
      Tabu(q1) := It.GetValue() + tabulength;
      Tabu(q2) := It.GetValue() + tabulength;

      It ++;

      println(It + " " + c.Violation + " (swapped "+ q1 + " and " + q2 + ")");

      if(minviolationplateau <= c.Violation.GetValue()) longueurplateau+=1 else longueurplateau = 0;
      minviolationplateau = minviolationplateau.min(c.Violation.GetValue());
      if (longueurplateau > 5){
        println("jump away");
        for (i <- 1 to N/5)Queens(SelectFrom(range)) :=: Queens(SelectFrom(range))
        longueurplateau = 0;
        minviolationplateau = c.Violation.GetValue();
      }
    }
    println(c.Violation);
    println(Queens.toList);
    println("run time: "+ getWatchString());
  }
}

Here is an output produced by this script:

NQueens(20)
run time after model close: 0:0:0:656
it:=1 Violation:=6 (swapped 11 and 19)
it:=2 Violation:=4 (swapped 12 and 14)
it:=3 Violation:=2 (swapped 13 and 1)
it:=4 Violation:=1 (swapped 4 and 2)
it:=5 Violation:=1 (swapped 1 and 10)
it:=6 Violation:=1 (swapped 8 and 17)
it:=7 Violation:=1 (swapped 18 and 5)
it:=8 Violation:=1 (swapped 9 and 16)
it:=9 Violation:=1 (swapped 19 and 11)
it:=10 Violation:=1 (swapped 9 and 4)
jump away
it:=11 Violation:=5 (swapped 1 and 3)
it:=12 Violation:=3 (swapped 4 and 14)
it:=13 Violation:=2 (swapped 17 and 2)
it:=14 Violation:=1 (swapped 12 and 0)
it:=15 Violation:=1 (swapped 7 and 18)
it:=16 Violation:=1 (swapped 16 and 3)
it:=17 Violation:=1 (swapped 17 and 4)
it:=18 Violation:=1 (swapped 18 and 0)
it:=19 Violation:=0 (swapped 8 and 9)
Violation:=0
List(queen0:=16, queen1:=13, queen2:=9, queen3:=14, queen4:=2, queen5:=10, queen6:=19, queen7:=0, queen8:=4, queen9:=18, queen10:=12, queen11:=17, queen12:=11, queen13:=7, queen14:=15, queen15:=6, queen16:=3, queen17:=1, queen18:=8, queen19:=5)
run time: 0:0:0:797