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.

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).