Introduction to implementing a model using Gecode/J

Starting pointers

This page will give you a simple introduction to implementing a model of a constraint problem as a script in Gecode/J. We assume that you have Gecode/J fully set-up on your computer, and that running the examples works.

To explain the way scripts look in Gecode/J, we will go through the Queens example, which can be found in the Queens.java file in the examples directory. The script also uses some common functionality in the Options class, which all examples use.

The Problem and the Model

The problem is to place n Queens on a chessboard of size n by n. The Queens should be placed in such a way that they do not attack each other, neither horizontally, vertically, nor diagonally.

The model for the Queens script is that we use a variable for each row i recording in which column we put the Queen (the variables will have an initial range of 0 to n-1). Choosing such a model, we get some of the constraints for free. The "free" constraints are that we place exactly n queens, and that each row has exactly one queen (the horizontal no attack constraint).

The rest of the constraints are specified using the following equations: for all combinations of i and j such that $i<j$ :

$\begin{eqnarray*} q_i & \neq & q_j \\ q_i + i & \neq & q_j + j \\ q_i - i & \neq & q_j - j \end{eqnarray*}$

The first equation enforces non-attacking vertically, and the second two equations diagonally.

General outline of a script

All example scripts in Gecode/J share the same structure. Not all of this structure is necessary, but it usually organizes the construction of a script fairly well. Each example Script is contained in a subclass of the Space class. The general outline is summarised in the code below.

import static org.gecode.Gecode.*;
import static org.gecode.GecodeEnumConstants.*;

public class Queens extends org.gecode.Space {
    private int n;
    private VarArray<IntVar> q;

    public Queens(Options opt) {
        super();
        <model>
    }

    public Queens(Boolean share, Queens queens) {
        super(share, queens);
        n = queens.n;
        q = new VarArray<IntVar>(this, share, queens.q);
    }

    public static void main(String[] args) {
        Options opt = new Options();
        opt.size = 6;
        opt.gui = true;
        opt.parse(args);
        opt.name = "" + opt.size + "-Queens";
        
        Queens queens = new Queens(opt);
        opt.doSearch(queens);
    }
}

The first two lines import the static definitions in Gecode and GecodeEnumConstants into the current namespace. This is done so that we can refer to constraints and names of, for example, relations using a direct interface. This emulates top-level functions as used in C and C++.

The class for the Queens model inherits from the class org.gecode.Space. This specific subclass encapsulates all the data of a particular search-state for the particular script.

The Data

The data for the Queens example is defined as

        public int n;
        public VarArray<IntVar> q;

The q member of the script manages the array of variables determining the column-position of the i th queen. The n member defines the size of the board used in the example. This value is necessarily the same as q.size(), but is stored as a member as a shorthand.

The Model

The constructor of the script class contains the initialization of the members of the class, definitions of all the constraints for the model, and the branching scheme used. The code for the model is divided as follows.

<model> +=
        <initialization>
        <constraints>
        <branching>

Initilization

Initialization of the data is rather straightforward, and looks as follows.

<initialization> +=
        n = opt.size;
        q = new VarArray<IntVar>(this, n, IntVar.class, 0, n-1);

The size of the Queens example is determined by the size-member of the Options class that is passed to the class by the main-function.

The construction of the variable array uses the arguments to specify the following things:

this: the Space to which the new variables belong.
n: the number of variables to create.
IntVar.class: the Class-instance from which to create the new variables. We use finite domain integer variables in this model.
0 and n-1: the starting range for each new variable.

For more information on how to construct variable arrays, see the VarArray class.

Constraints

The constraints of the model are defined as follows.

<constraints> +=
        int c[] = new int[n];

        for (int i=0; i<n; i++)
            c[i] = i;
        distinct(this, c, q, opt.icl);

        for (int i=0; i<n; i++)
            c[i] = -i;
        distinct(this, c, q, opt.icl);

        distinct(this, q, opt.icl);

The c-array contains the offsets used for implementing the diagonal differences. For example, the first for-loop sets the offset to be equivalent to the position in the array. The call distinct(this, c, q, opt.icl); posts the constraint that $\forall i.\forall j>i.\ q_i + i \neq q_j + j$ . The arguments to the call specify the following things:

this: the Space in which the constraint should be posted
c: the offsets to be used
q: the variables that the constraint constrains
opt.icl: the consistency level to use, i.e., how much pruning should be done.

The second distinct constraint behaves analogously. The third distinct is the normal distinct invocation without offsets. This constraint will enforce that no two queens are placed in the same column.

For more information about distinct constraints, see the documentation for Distinct constraints, and for more information about all the constraints that are available in Gecode/J, see Using finite domain integers and Using finite integer sets.

Branching

A Branching in Gecode determines the heuristic used for the non-deterministic choices made during search. For more information about branchings in general, see the Brief glossary.

The branching for the Queen-model is defined as follows:

<branching> +=
        branch(this, q, BVAR_SIZE_MIN, BVAL_MIN);

This call will make choices for the q-array based on the standard fail-first heuristic, i.e. find the variable with the smallest remaining domain-size (BVAR_SIZE_MIN), and try it's smallest value (BVAL_MIN). For more choices for the heuristics, see integer branchings and set branchings.

The copy constructor

The copy-constructor of the script was defined as follows:

    public Queens(Boolean share, Queens queens) {
        super(share, queens);
        n = queens.n;
        q = new VarArray<IntVar>(this, share, queens.q);
    }

Each script needs to have a copy-constructor defined. This constructor takes two arguments, a boolean called share and the instance that is being copied. The share-argument is for parallel execution, and when true, instances are allowed to share some data, since they are guaranteed to never use it concurrently. If you are only interested in implementing models, you can ignore the share-argument and just pass it on to the super constructor.

The copy-constructor should copy all data that it needs in the subsequent copies. Also, it must copy all of the variables that it needs to refer to later. This is done in the above copy-constructor for the variable array by using a constructor taking the new Space (i.e., this) and the old variable array (i.e. queens.q).

The toString method.

Gecode/J uses the toString() method of the script to present the contents. This method may be overridden in a Script, or the default one can be used.

The default implementation will return a string containing string representations of all the public variables and variable containers of the script. For example, for the Queens model, the first solution found would be presented as

q=[1,3,5,0,2,4]

For some problems, a custom toString()-method might give a more interesting representation, as is done for example in the Queens script that comes with Gecode/J.

The main function.

The main function of the script sets the options, constructs the initial Space (the root node of the search-tree) and runs the search.

For handling common options in examples, Gecode/J uses a class Options. The possible command-line arguments that Options knows how to handle are documented here. The method Options.doSearch(Space s) performs a search using the options specified.

The Queens example sets the standard size of the example to be 6 and to use graphical search using the Gecode/J Graphical Interactive Search Tool Gist. These options can be overridden by the user at the command-line when starting the program. The example is given the name n-Queens, with the actual n chosen when starting the program. This name is then shown in the title-bar of the Gist.

Conclusion

The full program-listing can be seen in the Queens.java file, which in addition to the above descriptions also includes a custom toString method.

For more inspiration on how to implement models in Gecode/J, see the list of examples that comes with Gecode/J.