Information Technology Reference
In-Depth Information
Figure 5.19.
A classroom scheduler
schedule-top.pl
% This program solves a classroom scheduling problem.
solution(P1,P2,P3,P4,P5) :-
uniq_periods(P1,P2,P3,P4,P5),
% All different periods.
not_2_in_a_row(P1,P2,P3,P4,P5),
% Not two consecutive hrs.
not_3_same_day(P1,P2,P3,P4,P5).
% Not three on the same day.
not_2_in_a_row(P1,P2,P3,P4,P5) :-
\+ seq(P1,P2), \+ seq(P1,P3), \+ seq(P1,P4), \+ seq(P1,P5),
\+ seq(P2,P3), \+ seq(P2,P4), \+ seq(P2,P5), \+ seq(P3,P4),
\+ seq(P3,P5), \+ seq(P4,P5).
seq(A,B) :- A =:= B-1.
seq(A,B) :- A =:= B+1.
not_3_same_day(P1,P2,P3,P4,P5) :-
\+ eqday(P1,P2,P3), \+ eqday(P1,P2,P4), \+ eqday(P1,P2,P5),
\+ eqday(P1,P3,P4), \+ eqday(P1,P3,P5), \+ eqday(P1,P4,P5),
\+ eqday(P2,P3,P4), \+ eqday(P2,P3,P5), \+ eqday(P2,P4,P5),
\+ eqday(P3,P4,P5).
eqday(A,B,C) :- Z is A // 100, Z is B // 100, Z is C // 100.
% The definition of uniq_periods is elsewhere.
Figure 5.20.
Previously scheduled periods
schedule-aux.pl
% Monday: only 11am and 1pm are available.
taken(X) :- X // 100 =:= 1, \+ X=111, \+ X=113.
% Tuesday: only 1pm and 2pm are available.
taken(X) :- X // 100 =:= 2, \+ X=213, \+ X=214.
% Wednesday: nothing available.
taken(X) :- X // 100 =:= 3.
% Thursday: all available, except for 10am, 12pm, and 2pm.
taken(410). taken(412). taken(414).
% Friday: nothing available.
taken(X) :- X // 100 =:= 5.
Want to read more?
This chapter was about the thinking required to solve constraint satisfaction problems.
As noted, the subarea of AI called
constraint programming
studies how to do this
efficiently. Work in this area began in the 1970s when Montanari [27] and Mackworth
