3.2. Basic Examples

3.2.1. N Queens

3.2.1.1. Problem Description

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:
  • Use a chessboard of n columns and n rows.
  • Place n queens on the chessboard.
  • No 2 queens can attack each other. A queen can attack any other queen on the same horizontal, vertical or diagonal line.
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

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

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.

3.2.1.2. Problem Size

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.

3.2.1.3. Domain Model

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 solutionQueencolumnIndexrowIndexascendingDiagonalIndex (columnIndex + rowIndex)descendingDiagonalIndex (columnIndex - rowIndex)
A1011 (**)-1
B010 (*)1 (**)1
C22240
D030 (*)33
When 2 queens share the same column, row or diagonal line, such as (*) and (**), they can attack each other.

3.2.2. Cloud Balancing

This example is explained in a tutorial.

3.2.3. Traveling Salesman (TSP - Traveling Salesman Problem)

3.2.3.1. Problem Description

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.

3.2.3.2. Problem Size

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.

3.2.3.3. Problem Difficulty

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:

3.2.4. Dinner Party

3.2.4.1. Problem Description

Miss Manners is throwing another dinner party.
  • This time she invited 144 guests and prepared 12 round tables with 12 seats each.
  • Every guest should sit next to someone (left and right) of the opposite gender.
  • And that neighbour should have at least one hobby in common with the guest.
  • At every table, there should be 2 politicians, 2 doctors, 2 socialites, 2 coaches, 2 teachers and 2 programmers.
  • And the 2 politicians, 2 doctors, 2 coaches and 2 programmers shouldn't be the same kind at a table.
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.

3.2.4.2. Problem Size

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

3.2.5. Tennis Club Scheduling

3.2.5.1. Problem Description

Every week the tennis club has 4 teams playing round robin against each other. Assign those 4 spots to the teams fairly.
Hard constraints:
  • Conflict: A team can only play once per day.
  • Unavailability: Some teams are unavailable on some dates.
Medium constraints:
  • Fair assignment: All teams should play an (almost) equal number of times.
Soft constraints:
  • Evenly confrontation: Each team should play against every other team an equal number of times.

3.2.5.2. Problem Size

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

3.2.5.3. Domain Model