Place n queens on a n sized chessboard so no 2 queens can attack each other. The most common n queens puzzle is the 8 queens puzzle, with n = 8:

Constraints:

This documentation heavily uses the 4 queens puzzle as the primary example.

A proposed solution could be:

Figure 3.1. A Wrong Solution for the 4 Queens Puzzle

The above solution is wrong because queens A1 and B0 can attack each other (so can queens B0 and D0). Removing queen B0 would respect the “no 2 queens can attack each other” constraint, but would break the “place n queens” constraint.

Below is a correct solution:

Figure 3.2. A Correct Solution for the 4 Queens Puzzle

All the constraints have been met, so the solution is correct. Note that most n queens puzzles have multiple correct solutions. We’ll focus on finding a single correct solution for a given n, not on finding the number of possible correct solutions for a given n.

4queens   has   4 queens with a search space of    256.
8queens   has   8 queens with a search space of   10^7.
16queens  has  16 queens with a search space of  10^19.
32queens  has  32 queens with a search space of  10^48.
64queens  has  64 queens with a search space of 10^115.
256queens has 256 queens with a search space of 10^616.

The implementation of the N queens example has not been optimized because it functions as a beginner example. Nevertheless, it can easily handle 64 queens. With a few changes it has been shown to easily handle 5000 queens and more.

Use a good domain model: it will be easier to understand and solve your planning problem. This is the domain model for the n queens example:

public class Column {

    private int index;

    // ... getters and setters
}

public class Row {

    private int index;

    // ... getters and setters
}

public class Queen {

    private Column column;
    private Row row;

    public int getAscendingDiagonalIndex() {...}
    public int getDescendingDiagonalIndex() {...}

    // ... getters and setters
}

A Queen instance has a Column (for example: 0 is column A, 1 is column B, …​) and a Row (its row, for example: 0 is row 0, 1 is row 1, …​). Based on the column and the row, the ascending diagonal line as well as the descending diagonal line can be calculated. The column and row indexes start from the upper left corner of the chessboard.

public class NQueens implements Solution<SimpleScore> {

    private int n;
    private List<Column> columnList;
    private List<Row> rowList;

    private List<Queen> queenList;

    private SimpleScore score;

    // ... getters and setters
}

A single NQueens instance contains a list of all Queen instances. It is the Solution implementation which will be supplied to, solved by and retrieved from the Solver. Notice that in the 4 queens example, NQueens’s getN() method will always return 4.

Table 3.2. A Solution for 4 Queens Shown in the Domain Model

A solution	Queen	columnIndex	rowIndex	ascendingDiagonalIndex (columnIndex + rowIndex)	descendingDiagonalIndex (columnIndex - rowIndex)
	A1	0	1	1 (**)	-1
	B0	1	0 (*)	1 (**)	1
	C2	2	2	4	0
	D0	3	0 (*)	3	3

When 2 queens share the same column, row or diagonal line, such as (*) and (**), they can attack each other.

Given a list of cities, find the shortest tour for a salesman that visits each city exactly once.

The problem is defined by Wikipedia. It is one of the most intensively studied problems in computational mathematics. Yet, in the real world, it’s often only part of a planning problem, along with other constraints, such as employee shift rostering constraints.

dj38     has  38 cities with a search space of   10^58.
europe40 has  40 cities with a search space of   10^62.
st70     has  70 cities with a search space of  10^126.
pcb442   has 442 cities with a search space of 10^1166.
lu980    has 980 cities with a search space of 10^2927.

Despite TSP’s simple definition, the problem is surprisingly hard to solve. Because it’s an NP-hard problem (like most planning problems), the optimal solution for a specific problem dataset can change a lot when that problem dataset is slightly altered:

Miss Manners is throwing another dinner party.

Drools Expert also has the normal Miss Manners example (which is much smaller) and employs an exhaustive heuristic to solve it. Planner’s implementation is far more scalable because it uses heuristics to find the best solution and Drools Expert to calculate the score of each solution.

wedding01 has 18 jobs, 144 guests, 288 hobby practicians, 12 tables and 144 seats with a search space of 10^310.

Every week the tennis club has 4 teams playing round robin against each other. Assign those 4 spots to the teams fairly.

Hard constraints:

Medium constraints:

Soft constraints:

munich-7teams has 7 teams, 18 days, 12 unavailabilityPenalties and 72 teamAssignments with a search space of 10^60.

Assign each meeting to a starting time and a room. Meetings have different durations.

Hard constraints:

Medium constraints:

Soft constraints:

50meetings-160timegrains-5rooms  has  50 meetings, 160 timeGrains and 5 rooms with a search space of 10^145.
100meetings-320timegrains-5rooms has 100 meetings, 320 timeGrains and 5 rooms with a search space of 10^320.