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.
In the directory
/drools-solver/drools-solver-examples/
run the
following command:
$ mvn exec:exec -Dexec.mainClass="org.drools.solver.examples.nqueens.app.NQueensApp" ...
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:
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.
Below is a correct solution:
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.
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 |
---|---|---|---|---|
4 | 256 | 2 | 2 | 128 |
8 | 16777216 | 64 | 64 | 262144 |
16 | 18446744073709551616 | 14772512 | 14772512 | 1248720872503 |
32 | 1.46150163733090291820368483e+48 | ? | ? | ? |
64 | 3.94020061963944792122790401e+115 | ? | ? | ? |
n | n ^ n | ? | # feasible solutions | ? |
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:
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 solution | Queen | x | y | ascendingD (x + y) | descendingD (x - y) |
---|---|---|---|---|---|
![]() | A1 | 0 | 1 | 1 (**) | -1 |
B0 | 1 | 0 (*) | 1 (**) | 1 | |
C2 | 2 | 2 | 4 | 0 | |
D0 | 3 | 0 (*) | 3 | 3 |
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.
In the directory
/drools-solver/drools-solver-examples/
run the
following command:
$ mvn exec:exec -Dexec.mainClass="org.drools.solver.examples.lessonschedule.app.LessonScheduleApp" ...
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.
Here is a screenshot of the example:
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.
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 |
---|---|---|---|---|---|---|
4 | 6 | 12 | 2176782336 | <= 518400 | ? | 1? |
6 | 10 | 30 | 1000000000000000000000000000000 | <= 47784725839872000000 | ? | 1? |
8 | 14 | 56 | 1.52464943788290465606136043e+64 | <= 5.77608277425558771434498864e+43 | ? | 1? |
10 | 18 | 90 | 9.43029892325559280477052413e+112 | <= 1.07573451027871200629339068e+79 | ? | 1? |
12 | 22 | 132 | 1.58414112478195320415135060e+177 | <= 2.01650616733413376416949843e+126 | ? | 1? |
14 | 26 | 182 | 3.35080635695103223315189511e+257 | <= 1.73513467024013808570420241e+186 | ? | 1? |
16 | 30 | 240 | 3.22924601799855400751522483e+354 | <= 2.45064610271441678267620602e+259 | ? | 1? |
n | 2 * (n - 1) | n * (n - 1) | (2 * (n - 1)) ^ (n * (n - 1)) | <= (((2 * (n - 1))!) ^ (n / 2)) | ? | 1? |
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" ...
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.
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_set1 | 7883 | 607 | 54 | 7 | 1.11000574474221096210367623e+1052 | ? | 1? |
exam_comp_set2 | 12484 | 870 | 40 | 49 | 2.86903028422562597982749122e+5761 | ? | 1? |
exam_comp_set3 | 16365 | 934 | 36 | 48 | 5.74648299136737635070728795e+5132 | ? | 1? |
exam_comp_set4 | 4421 | 273 | 21 | 1 | 1.44349601026818742275741580e+51 | ? | 1? |
exam_comp_set5 | 8719 | 1018 | 42 | 3 | ? | 1? | |
exam_comp_set6 | 7909 | 242 | 16 | 8 | ? | 1? | |
exam_comp_set7 | 13795 | 1096 | 80 | 28 | ? | 1? | |
exam_comp_set8 | 7718 | 598 | 80 | 8 | ? | 1? | |
? | s | t | p | r | (t ^ p) ^ r | ? | 1? |
Below you can see the main examination domain classes:
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.