Information Technology Reference
In-Depth Information
Figure 5.18.
A scheduling problem
The task is to schedule a new class to meet five hours each week.
Meeting times are on the hour from 9am to 4pm, on weekdays.
Some of the periods will be taken by previously scheduled activities.
Classes must not meet on successive hours on the same day, or for
more than two hours total on any one day.
This says that the zebra is in house 5, the rightmost house. But who lives there? To
find out, use a
print_solution
predicate defined as follows:
print_solution :-
solution(Zeb,E,S,U,J,N), pmatch(Zeb,E,'English'),
pmatch(Zeb,S,'Spanish'), pmatch(Zeb,U,'Ukrainian'),
pmatch(Zeb,J,'Japanese'), pmatch(Zeb,N,'Norwegian').
pmatch(X,X,Name) :-
% Write when there is a match.
nl, write('The zebra owner is '), write(Name).
pmatch(X,Y,Name) :- \+ X=Y.
% Write nothing in this case.
The
print_solution
predicate uses the positional information to print the nationality
that
matches
the zebra house number:
?- print_solution.
The zebra owner is Japanese
∗
5.6 A fifth example: Scheduling
The constraint satisfaction problem in this section is not a puzzle at all, but rather a
much more practical problem,
scheduling
. Examples of scheduling include assigning
people to jobs, or meetings to rooms, or courses to final exam periods. Solving prob-
lems like these still requires thinking of course, but now the thinking is not done just
for the fun of it, as with puzzles.
A scheduling problem involving the timetable for a course is shown in figure 5.18.
The task is to find
periods
(that is, the days and times) for the five classes. This can be
formulated as a constraint satisfaction problem as follows:
Variables:
P
1
,
P
2
,
P
3
,
P
4
,
P
5
, where each
P
i
is a period for the course.
