Clone wiki

OscaR / StartCBLS

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 Oscar.cbls.

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 Oscar.cbls 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.

package oscar.examples.cbls.queens

import oscar.cbls.modeling.Algebra._
import oscar.cbls.constraints.core._
import oscar.cbls.modeling._
import oscar.util._
import oscar.cbls.invariants.core.computation.CBLSIntVar

/**
 * Local Search for NQueens
 * Moves are operated by swapping variables
 */
object NQueensEasy1 extends CBLSModel with App{

  //starts a stopwatch
  startWatch()

  //declaring some constants of the problem
  val N = 20
  val range = 0 to N-1
  val tenure = 3

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

  val rand = new scala.util.Random()

  // initial solution
  val init = rand.shuffle((0 to N-1).toList).toArray

  //here are created the variables of the problem
  //notice that we are using the implicit model declared by CBLSModel

  val queens = Array.tabulate(N)(q => CBLSIntVar(0 to N-1,init(q),"queen" + q))

  //here are created the constraints of the problem
  //notice that we are posting the constraint in the implicit constraint system declared by CBLSMomdel
  //alldiff on rows in enforced because we swap queens initially different
  c.add(allDifferent(Array.tabulate(N)(q => (queens(q) + q).toIntVar)))
  c.add(allDifferent(Array.tabulate(N)(q => (q - queens(q)).toIntVar)))

  close()

  //this tabu search is a bit simplistic: does not use the invariants for maintaining Tabu...
  //and max violated queens might be all tabu

  var it = 0
  val tabu = Array.fill(N)(0)


  while(violation.value > 0){
    selectMin(range,range)(
      (p,q) => swapVal(queens(p),queens(q)),
      (p,q) => tabu(p) < it && tabu(q) < it && p < q)
    match{
      case (q1,q2) =>
        queens(q1) :=: queens(q2)
        tabu(q1)= it + tenure
        tabu(q2) = it + tenure
      case _ => println("Warning: Tabu it too big compared to queens count")
    }
    it += 1
  }

  println(getWatchString)
  println(it)
  println(queens.mkString(","))
}

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 Oscar.cbls: 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 oscar.examples.cbls.queens

import oscar.cbls.modeling.CBLSModel
import oscar.cbls.invariants.core.computation.{CBLSSetVar, CBLSIntVar}
import scala.language.postfixOps

/**
 * Created by rdl on 13/01/14.
 */
object NQueensEasy2 extends CBLSModel with App{

  val N = 20

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

  val rand = new scala.util.Random()

  startWatch()

  // initial solution
  val init = rand.shuffle((0 to N-1).toList).toArray

  val queens = Array.tabulate(N)(q => CBLSIntVar(0 to N-1,init(q),"queen_" + q))

  //alldiff on rows in enforced because we swap queens initially different
  add(allDifferent(Array.tabulate(N)(q => (queens(q) + q).toIntVar)))
  add(allDifferent(Array.tabulate(N)(q => (q - queens(q)).toIntVar)))

  val violationArray:Array[CBLSIntVar] = Array.tabulate(N)(q => c.violation(queens(q))).toArray

  val tabu:Array[CBLSIntVar] = Array.tabulate(N)(q => intVar(0 to Int.MaxValue, 0, "tabu_queen" + q))
  val it = intVar(0 to Int.MaxValue,1,"it")
  val nonTabuQueens:CBLSSetVar = selectLESetQueue(tabu, it)
  val nonTabuMaxViolQueens:CBLSSetVar = argMax(violationArray, nonTabuQueens)

  close()

  val tabulength = 3

  while((violation.value > 0) && (it.value < N)){

    val oldviolation:Int = violation.value

    selectFirstDo(nonTabuMaxViolQueens.value)((q1:Int) => {
      selectFirstDo(nonTabuQueens.value, (q2:Int) => {
        q2!=q1 && c.swapVal(queens(q1),queens(q2)) < oldviolation
      })((q2:Int) => {
        println("" + it.value + " swapping " + q1 +"(tabu: " + tabu(q1) + ") and " + q2 +"(tabu: " + tabu(q2) + ")")
        queens(q1) :=: queens(q2)
        tabu(q1) := it.value + tabulength
        tabu(q2) := it.value + tabulength

      },()=>println("Warning: Tabu it too big compared to queens count"))},
      ()=>println("Warning: Tabu it too big compared to queens count"))

    it ++
  }

  println(getWatchString)
  println(it)
  println(queens.mkString(","))
}

Updated