Solver examples

Introduction

Drools-solver has several examples. In this manual we explain drools-solver mainly using the n queens example. So it's advisable to read at least the section about that example.

The n queens example

Running the example

In the directory /drools-solver/drools-solver-examples/ run the following command:

$ mvn exec:exec -Dexec.mainClass="org.drools.solver.examples.nqueens.app.NQueensApp"
...

Screenshot

Here is a screenshot of the example:

Figure 1.1. Screenshot of the n queens example

Screenshot of the n queens example

Problem statement

The n queens puzzle is a puzzle with the follow constraints:

  • Use a chessboard of n rows and n columns.

  • Place n queens on the chessboard.

  • No 2 queens can attack each other. Note that a queen can attack any other queen on the same horizontal, vertical or diagonal line.

The most common n queens puzzle is the 8 queens puzzle, with n = 8. We 'll explain drools-solver using the 4 queens puzzle as the primary example.

A proposed solution could be:

Figure 1.2. 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 (as 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.

Solution(s)

Below is a correct solution:

Figure 1.3. 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.

Problem size

These numbers might give you some insight on the size of this problem.

Table 1.1. NQueens problem size

# queens (n)# possible solutions (each queen it's own column)# feasible solutions (distinct)# optimal solutions (distinct)# possible / # optimal
425622128
8167772166464262144
161844674407370955161614772512147725121248720872503
321.46150163733090291820368483e+48???
643.94020061963944792122790401e+115???
nn ^ n?# feasible solutions?

Domain class diagram

Use a good domain model and it will be easier to understand and solve your problem with drools-solver. We 'll use this domain model for the n queens example:

Figure 1.4. NQueens domain class diagram

NQueens domain class diagram

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

Table 1.2. A solution for the 4 queens puzzle shown in the domain model

A solutionQueenxyascendingD (x + y)descendingD (x - y)
A1011 (**)-1
B010 (*)1 (**)1
C22240
D030 (*)33

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

You can find the source code of this example (as well as well as several other examples) in the drools-solver-examples src distribution.

The lesson schedule example

Running the example

In the directory /drools-solver/drools-solver-examples/ run the following command:

$ mvn exec:exec -Dexec.mainClass="org.drools.solver.examples.lessonschedule.app.LessonScheduleApp"
...

Screenshot

Here is a screenshot of the example:

Figure 1.5. Screenshot of the lesson schedule example

Screenshot of the lesson schedule example

Problem statement

Schedule lessons with the follow constraints:

  • No teacher with 2 lessons in the same timeslot

  • No group with 2 lessons in the same timeslot

The traveling tournament example

Running the example

In the directory /drools-solver/drools-solver-examples/ run one of the the following commands:

$ mvn exec:exec -Dexec.mainClass="org.drools.solver.examples.travelingtournament.app.simple.SimpleTravelingTournamentApp"
...
$ mvn exec:exec -Dexec.mainClass="org.drools.solver.examples.travelingtournament.app.smart.SmartTravelingTournamentApp"
...

The smart implementation performs and scales a lot better than the simple implementation.

Screenshot

Here is a screenshot of the example:

Figure 1.6. Screenshot of the traveling tournament example

Screenshot of the traveling tournament example

Problem statement

Schedule matches between teams with the following hard constraints:

  • Each team plays twice against every other team: once home and once away

  • Each team has exactly 1 match on each playing day

  • No more than 3 consecutive home or 3 consecutive away matches for any team

  • No repeaters: 2 consecutive matches of the same 2 teams (so each team plays once home and once away

and the following soft constraints:

  • Minimize the total distance traveled of all teams.

You can find a detailed description as well as several records of this problem here.

Problem size

These numbers might give you some insight on the size of this problem.

Table 1.3. Traveling tournament problem size

# teams# days# matches# possible solutions (simple)# possible solutions (smart)# feasible solutions# optimal solutions
46122176782336<= 518400?1?
610301000000000000000000000000000000<= 47784725839872000000?1?
814561.52464943788290465606136043e+64<= 5.77608277425558771434498864e+43?1?
1018909.43029892325559280477052413e+112<= 1.07573451027871200629339068e+79?1?
12221321.58414112478195320415135060e+177<= 2.01650616733413376416949843e+126?1?
14261823.35080635695103223315189511e+257<= 1.73513467024013808570420241e+186?1?
16302403.22924601799855400751522483e+354<= 2.45064610271441678267620602e+259?1?
n2 * (n - 1)n * (n - 1)(2 * (n - 1)) ^ (n * (n - 1))<= (((2 * (n - 1))!) ^ (n / 2))?1?

The ITC2007 examination example

Running the example

In the directory /drools-solver/drools-solver-examples/ run the following command:

$ mvn exec:exec -Dexec.mainClass="org.drools.solver.examples.itc2007.examination.app.ExaminationApp"
...

Screenshot

Here is a screenshot of the example:

Figure 1.7. Screenshot of the examination example

Screenshot of the examination example

Problem statement

Schedule each exam into a period and into a room. Multiple exams can share the same room during the same period.

There are a number of hard constraints that cannot be broken:

  • Exam conflict: 2 exams that share students should not occur in the same period.

  • Room capacity: A room's seating capacity should suffice at all times.

  • Period duration: A period's duration should suffice for all of its exams.

  • Period related hard constraints should be fulfilled:

    • Coincidence: 2 exams should use the same period (but possibly another room).

    • Exclusion: 2 exams should not use the same period.

    • After: 1 exam should occur in a period after another exam's period.

  • Room related hard constraints should be fulfilled:

    • Exclusive: 1 exam should not have to share its room with any other exam.

There are also a number of soft constraints that should be minimized (each of which has parameterized penalty's):

  • 2 exams in a row.

  • 2 exams in a day.

  • Period spread: 2 exams that share students should be a number of periods apart.

  • Mixed durations: 2 exams that share a room should not have different durations.

  • Front load: Large exams should be scheduled earlier in the schedule.

  • Period penalty: Some periods have a penalty when used.

  • Room penalty: Some rooms have a penalty when used.

It uses large test data sets of real-life universities.

You can find a more detailed description of this problem here.

Problem size

These numbers might give you some insight on the size of this problem.

Table 1.4. Examination problem size

Set# students# exams/topics# periods# rooms# possible solutions# feasible solutions# optimal solutions
exam_comp_set178836075471.11000574474221096210367623e+1052?1?
exam_comp_set21248487040492.86903028422562597982749122e+5761?1?
exam_comp_set31636593436485.74648299136737635070728795e+5132?1?
exam_comp_set444212732111.44349601026818742275741580e+51?1?
exam_comp_set587191018423 ?1?
exam_comp_set67909242168 ?1?
exam_comp_set71379510968028 ?1?
exam_comp_set87718598808 ?1?
?stpr(t ^ p) ^ r?1?

Domain class diagram

Below you can see the main examination domain classes:

Figure 1.8. Examination domain class diagram

Examination domain class diagram

Notice that we've split up the exam concept into an Exam class and a Topic class. The Exam instances change during solving, when they get another period or room. The Topic, Period and Room instances never change during solving.