Here's how we generate it:

    private NQueens createNQueens(int n) {
        NQueens nQueens = new NQueens();
        nQueens.setId(0L);
        List<Queen> queenList = new ArrayList<Queen>(n);
        for (int i = 0; i < n; i++) {
            Queen queen = new Queen();
            queen.setId((long) i);
            queen.setX(i); // Different column
            queen.setY(0); // Same row
            queenList.add(queen);
        }
        nQueens.setQueenList(queenList);
        return nQueens;
    }

The starting solution will probably be far from optimal (or even feasible). Here, it's actually the worst possible solution. However, we 'll let the solver find a much better solution for us anyway.

After a problem is solved, you can reuse the same solver instance to solve another problem (of the same problem type).

In this starting solution the multipleQueensHorizontal score rule will fire for 6 queen couples: (A, B), (A, C), (A, D), (B, C), (B, D) and (C, D). Because none of the queens are on the same vertical or diagonal line, this starting solution will have a score of -6. An optimal solution of 4 queens has a score of 0.

You need to add your score rules drl files in the solver configuration, for example:

    <scoreDrl>/org/drools/solver/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>

You can add multiple <scoreDrl> entries if needed.

It's recommended to use drools in forward-chaining mode (which is the default behaviour), as for solver implementations this will create the effect of a delta based score calculation instead of a full score calculation on each solution evaluation. For example, if a single queen moves from y 0 to 3, it won't bother to recalculate the "multiple queens on the same horizontal line" constraint for queens with y 1 or 2. This is a huge performance gain. Drools-solver gives you this huge performance gain without forcing you to write a very complicated delta based score calculation algorithm. Just let the drools rule engine do the hard work.

Adding more constraints is easy and scalable (once you understand the drools rule syntax). This allows you to add it a bunch of soft constraint score rules on top of the hard constraints score rules with little effort and at a reasonable performance cost. For example, for a freight routing problem you could add a soft constraint to avoid the certain flagged highways at rush hour.

A move can have a small or large impact. In the above example, the move of queen C0 to C2 is a small move. Some moves are the same move type. These are some possibilities for move types in n queens:

Because we have decided that all queens will be on the board at all times and each queen has an appointed column (for performance reasons), only the first 2 move types are usable in our example. Furthermore, we 're only using the first move type in the example because we think it gives the best performance, but you are welcome to prove us wrong.

Each of your move types will be an implementation of the Move interface:

public interface Move {

    boolean isMoveDoable(EvaluationHandler evaluationHandler);

    Move createUndoMove(EvaluationHandler evaluationHandler);

    void doMove(EvaluationHandler evaluationHandler);

}

Let's take a look at the Move implementation for 4 queens which moves a queen to a different row:

public class YChangeMove implements Move {

    private Queen queen;
    private int toY;

    public YChangeMove(Queen queen, int toY) {
        this.queen = queen;
        this.toY = toY;
    }

    // ... see below

}

An instance of YChangeMove moves a queen from it's current y to a different y.

Drool-solver calls the doMove(WorkingMemory) method to do a move. The Move implementation must notify the working memory of any changes it does on the solution facts:

    public void doMove(WorkingMemory workingMemory) {
        FactHandle queenHandle = workingMemory.getFactHandle(queen);
        workingMemory.modifyRetract(queenHandle); // before changes are made
        queen.setY(toY);
        workingMemory.modifyInsert(queenHandle, queen); // after changes are made
    }

Drools-solver disables shadow facts for increased performance, so you cannot use the workingMemory.update(FactHandle, Object) method, instead you need to call the workingMemory.modifyRetract(FactHandle) method before modifying the fact and the workingMemory.modifyInsert(FactHandle, Object) method after modifying the fact. Note that you can alter multiple facts in a single move and effectively create a big move (also known as a coarse-grained move).

Drools-solver automatically filters out non doable moves by calling the isDoable(WorkingMemory) method on a move. A non doable move is:

In the n queens example, a move which moves the queen from it's current row to the same row isn't doable:

    public boolean isMoveDoable(WorkingMemory workingMemory) {
        int fromY = queen.getY();
        return fromY != toY;
    }

Because we won't generate a move which can move a queen outside the board limits, we don't need to check it. A move that is currently not doable can become doable on a later solution.

Each move has an undo move: a move (usually of the same type) which does the exact opposite. In the above example the undo move of C0 to C2 would be the move C2 to C0. An undo move can be created from a move, but only before the move has been done on the current solution.

    public Move createUndoMove(WorkingMemory workingMemory) {
        return new YChangeMove(queen, queen.getY());
    }

Notice that if C0 would have already been moved to C2, the undo move would create the move C2 to C2, instead of the move C2 to C0.

The local search solver can do and undo a move more than once, even on different (successive) solutions.

A move must implement the equals() and hashcode() methods. 2 moves which make the same change on a solution, must be equal.

    public boolean equals(Object o) {
        if (this == o) {
            return true;
        } else if (o instanceof YChangeMove) {
            YChangeMove other = (YChangeMove) o;
            return new EqualsBuilder()
                    .append(queen, other.queen)
                    .append(toY, other.toY)
                    .isEquals();
        } else {
            return false;
        }
    }

    public int hashCode() {
        return new HashCodeBuilder()
                .append(queen)
                .append(toY)
                .toHashCode();
    }

In the above example, the Queen class uses the default Object equal() and hashcode() implementations. Notice that it checks if the other move is an instance of the same move type. This is important because a move will be compared to a move with another move type if you're using more then 1 move type.

It's also recommended to implement the toString() method as it allows you to read drools-solver's logging more easily:

    public String toString() {
        return queen + " => " + toY;
    }

Now that we can make a single move, let's take a look at generating moves.

As you can see, not all the moves are doable. At the starting solution we have 12 doable moves (n * (n - 1)), one of which will be move which changes the starting solution into the next solution. Notice that the number of possible solutions is 256 (n ^ n), much more that the amount of doable moves. Don't create a move to every possible solution. Instead use moves which can be sequentially combined to reach every possible solution.

It's highly recommended that you verify all solutions are connected by your move set. This means that by combining a finite number of moves you can reach any solution from any solution. Otherwise you're already excluding solutions at the start. Especially if you're using only big moves, you should check it. Just because big moves outperform small moves in a short test run, it doesn't mean that they will outperform them in a long test run.

You can mix different move types. Usually you're better off preferring small (fine-grained) moves over big (course-grained) moves because the score delta calculation will pay off more. However, as the traveling tournament example proves, if you can remove a hard constraint by using a certain set of big moves, you can win performance and scalability. Try it yourself: run both the simple (small moves) and the smart (big moves) version of the traveling tournament example. The smart version evaluates a lot less unfeasible solutions, which enables it to outperform and outscale the simple version.

Move generation currently happens with a MoveFactory:

public class NQueensMoveFactory extends CachedMoveListMoveFactory {

    public List<Move> createMoveList(Solution solution) {
        NQueens nQueens = (NQueens) solution;
        List<Move> moveList = new ArrayList<Move>();
        for (Queen queen : nQueens.getQueenList()) {
            for (int n : nQueens.createNList()) {
                moveList.add(new YChangeMove(queen, n));
            }
        }
        return moveList;
    }

}

But we'll be making move generation part of the drl's soon.

Because the move B0 to B3 has the highest score (-3), it is picked as the next step. Notice that C0 to C3 (not shown) could also have been picked because it also has the score -3. If multiple moves have the same highest score, one is picked randomly, in this case B0 to B3.

The step is made and from that new solution, the local search solver tries all the possible moves again, to decide the next step after that. It continually does this in a loop, and we get something like this:

Notice that the local search solver doesn't use a search tree, but a search path. The search path is highlighted by the green arrows. At each step it tries all possible moves, but unless it's the step, it doesn't investigate that solution further. This is one of the reasons why local search is very scalable.

As you can see, the local search solver solves the 4 queens problem by starting with the starting solution and make the following steps sequentially:

If we turn on INFO logging, this is reflected into the logging:

INFO  Solving with random seed (0).
INFO  Initial score (-6) is starting best score. Updating best solution and best score.
INFO  Step (0), time spend (0) doing next step ([Queen-1] 1 @ 0 => 3).
INFO  New score (-3) is better then last best score (-6). Updating best solution and best score.
INFO  Step (1), time spend (0) doing next step ([Queen-3] 3 @ 0 => 2).
INFO  New score (-1) is better then last best score (-3). Updating best solution and best score.
INFO  Step (2), time spend (15) doing next step ([Queen-0] 0 @ 0 => 1).
INFO  New score (0) is better then last best score (-1). Updating best solution and best score.
INFO  Solved in 3 steps and 15 time millis spend.

Notice that the logging used the toString() method from our Move implementation: [Queen-1] 1 @ 0 => 3.

The local search solver solves the 4 queens problem in 3 steps, by evaluating only 37 possible solutions (3 steps with 12 moves each + 1 starting solution), which is only fraction of all 256 possible solutions. It solves 16 queens in 31 steps, by evaluating only 7441 out of 18446744073709551616 possible solutions.

In the above example the selector generated the moves shown with the blue lines, the accepter accepted all of them and the forager picked the move B0 to B3.

If we turn on DEBUG logging, we can see the decision making in the log:

INFO  Solving with random seed (0).
INFO  Initial score (-6) is starting best score. Updating best solution and best score.
DEBUG     Move ([Queen-0] 0 @ 0 => 0) ignored because not doable.
DEBUG     Move ([Queen-0] 0 @ 1 => 1) with score (-4) and acceptChance (1.0).
DEBUG     Move ([Queen-0] 0 @ 2 => 2) with score (-4) and acceptChance (1.0).
...
DEBUG     Move ([Queen-1] 1 @ 3 => 3) with score (-3) and acceptChance (1.0).
...
DEBUG     Move ([Queen-3] 3 @ 3 => 3) with score (-4) and acceptChance (1.0).
INFO  Step (0), time spend (0) doing next step ([Queen-1] 1 @ 0 => 3).
INFO  New score (-3) is better then last best score (-6). Updating best solution and best score.
...