Here is a short cookbook showing you how to solve a very simple CLP (Constraint Language Programming) problem using the WASA framework.

Presenting the problem

The goal is to place N queens on a N * N chessboard so that no two queens attack each other. This means that two queens cannot be placed on the same line / column / diagonal.

The code snippets belows are taken out from fr.jussieu.gla.wasa.samples.queens.NaiveQueens.

Presenting the algorithm

In order to be solved by WASA, the problem should be expressed as follows :

• a queen position is said to be a Var.
• the elementary terms of the problem are translated into Constraints, which say "how a Var good is". For instance, if two queens are placed on the same column, their Var error is incremented.
• an Explorer is able to choose new positions for the queen which has the Var with the highest error.

A Configuration represents the state of all queens on the board. The WASA solver will "shake" the configurations in order to find the "best" (as expressed by Constraints) as follows :

1. Place the queens on the chessboard randomly, as the start Configuration.
2. Choose the "worst" Var as expressed by Constraints.
3. Use Explorer to find other possible values for this Var, leading to neighbour Configurations.
4. If a global improvement has been found then go to step 2, else go to step 1.

Creating Buisness Objects

The n-queens problem is modelled by a very simple Buisness Object :

In order to simplify the problem, we'll declare each queen on a different line. This will implicitly satisfy the Constraint "two queens cannot be placed on the same line".

The board itself can be simply modelled by a Queen array :

  Queen[] queens = new Queen[ boardSize ] ;
  for( int i = 0 ; i < boardSize ; i++ ) {
    queens[ i ] = new Queen( i , i ) ;
  }

Creating the Problem

The fr.jussieu.gla.wasa.core.Problem is the placeholder for the problem definition. All problem elements (Var, Constraint, Explorer...) require a valid Problem instance in their constructor.

  Problem problem = new Problem() ;

Creating the Vars

Each Buisness Object property which appears in a Constraint should be mapped by a fr.jussieu.gla.wasa.core.Var object.

We'll use an utility class which uses reflection to map a var to a Buisness Object property, given the property name. Remember we'll only apply Constraints on queens' columns, so we only map the Column property for each Queen instance :

  final Var[] varColumns = new Var[ boardSize ] ;
	
  for( int i = 0 ; i < boardSize ; i++ ) {
    varColumn[ i ] = VarFactory.INSTANCE.createPropertyVar(
        columnExplorer , queens[ i ] , "Column" ) ;
  }

We'll explain the role of the columnExplorer later, just remember that it is an Explorer instance, required by Var constructor.

Creating the Constraints

A fr.jussieu.gla.wasa.core.Constraint expresses how Vars "good" are. Constraints rely on Buisness Objects properties to determine the error to assign to Vars.

Let's take the constraint of different columns. This should be expressed as "if two queens are on the same column, increment their error respectively" :

  Constraint columnsAllDifferent = new Constraint( problem ) {
    public void evaluate() {
      for( int i = 0 ; i < boardSize - 1 ; i++ ) {
        for( int j = i + 1 ; j < boardSize ; j++ ) {
          if( queens[ i ].getColumn() == queens[ j ].getColumn() ) {
            varColumns[ i ].incError( 1 ) ;
            varColumns[ j ].incError( 1 ) ;
          }
        }
      }
    }
  } ;

It is also possible to give a name to the constraint for debugging purpose :

  columnsAllDifferent.setName( "N->S" ) ;

The constraints on the diagonals follow the same idea.

Creating the Explorer

A fr.jussieu.gla.wasa.core.Explorer provides new meaningful values for the worst Var of a given Configuration. The set of modified Configurations is called a Neighbourhood.
The WASA solver chooses the Var, and calls Explorer.explore while Explorer.hasNeighbours returns true. The exploreIndex parameter passed to both methods is a convenience for avoiding the programmer to implement his own counter. Explorer.explore returns true if it produced a configuration which should be taken in account, false otherwhise.

  Explorer columnExplorer = new Explorer( problem ) {


    protected boolean hasNeighbours( int exploreIndex ) {
      return exploreIndex < boardSize ;
    }

    public boolean explore( int exploreIndex ) {
      int varRank = getVar().getRank() ;
      if ( exploreIndex == 0 ) {
        return false ;
      } else {
        int theColumn = queens[ varRank ].getColumn() ;
        int newColumn = ( theColumn + exploreIndex ) % boardSize ;
        queens[ varRank ].setColumn( newColumn ) ;      
        return true ;
      }
    }
  } ;

Please note that the code above accesses Buisness Objects directly. It just uses Explorer.getVar in order to retrieve the current worst Var (according to the latest Constraints evaluation). The rank of the Var means it was the n^th Var created for the Problem.

Let's see what happens when the Explorer is being called by the WASA solver :

Here is the start configuration :		Possible moves for the red queen is to try other columns on the same line :

The Explorer instance is called several times by WASA, with the following results :

exploreIndex	hasNeighbours( exploreIndex ) return value	Configuration set by explore	explore( exploreIndex ) return value
0	true		false => not taken in account
1	true		true
2	true		true
3	true		true
4	false => means don't perform any other iteration.	-	-

At the end of the exploration, the best configuration will be retained by the WASA solver as the next start Configuration. If no improvement was found, a random Configuration is set.

Creating the Random Configurator

Due to the stochastic approach, the WASA solver may "shake" Buisness Objects when a dead-end (aka : local minimum) is detected. An instance of fr.jussieu.gla.wasa.core.RandomConfigurator provides a Buisness Object-dependant way to "shake" them :

  RandomConfigurator randomConfigurator = new RandomConfigurator( problem ) {
	
    public void configure( float randomRatio ) {
		
      IntRandomIterator randomQueenChoice =
        new IntRandomIterator( 0, boardSize -1 ) ;
				
      int bound = (int) ( randomRatio * boardSize ) ;
			
      for( int i = 0 ; i < bound ; i++ ) {
        queens[ randomQueenChoice.nextInt() ].setColumn(
            (int) ( Math.random() * boardSize )
        ) ;
      }
    }
  } ;

Putting it all together

The Problem will be solved by a fr.jussieu.gla.wasa.core.Engine which runs the Adaptative Search Algorithm :

  Engine engine = new Engine( problem ) ;
  engine.runQuiet( 1000, 0.0f ) ;
  engine.restoreBest() ;

The engine will search a configuration with an error of 0.0f on constraints, by executing at most 1000 steps. Then, our queens are set to columns which represent the best configuration found.

(The snippet above is located in fr.jussieu.gla.wasa.samples.queens.NaiveQueensSample)

Conclusion

In this document, we hid some implementation details, like problem-dependant tuning of the Engine, or solution display. The source code is available in fr.jussieu.gla.wasa.samples.queens.NaiveQueens.