使用Prolog实现多约束课程时间表调度的编程问题求助

解题核心思路 #

这道题是典型的有限域约束满足问题，落地Prolog实现只要做好三件事就不会出错：

1. 统一所有时间槽的表示格式，不要混用字符串描述，避免冲突判断逻辑失效
2. 枚举所有课程的可选班次
3. 逐条校验约束：无课程时间冲突、每天预留午餐时间

步骤1：统一时间建模 #

把所有出现的时段映射为结构化二元组(星期, 时段数字)，其中数字12代表noon、13代表1点、14代表2点、15代表3点，其余小时数直接对应数字即可。
按题目描述整理所有课程可选班次：

• 艺术课2个班次：MWF10、MWF11
• 舞蹈课1个班次：周五1-4点（共3课时，占周五13、14、15三个时段）
• 音乐课2个班次：
  • 班次1：周一11、周三15、周五15
  • 班次2：周一14、周三14、周五11
• 电影课2个班次：
  • 班次1：周一11、周三11、周五12
  • 班次2：周一12、周三12、周三15

步骤2：完整实现代码 #

% 定义所有课程的可选班次及对应时间列表
art(art_mwf10, [(mon,10), (wed,10), (fri,10)]).
art(art_mwf11, [(mon,11), (wed,11), (fri,11)]).

dance(dance_fri1_4, [(fri,13), (fri,14), (fri,15)]).

music(music1, [(mon,11), (wed,15), (fri,15)]).
music(music2, [(mon,14), (wed,14), (fri,11)]).

film(film1, [(mon,11), (wed,11), (fri,12)]).
film(film2, [(mon,12), (wed,12), (wed,15)]).

% 辅助谓词：判断两个时间列表无重叠
no_conflict([], _).
no_conflict([Time|Rest], OtherTimes) :-
    \+ member(Time, OtherTimes),
    no_conflict(Rest, OtherTimes).

% 辅助谓词：校验三天均有可用午餐时间（12点或13点空闲）
valid_lunch(AllTimes) :-
    % 周一
    (\+ member((mon,12), AllTimes) ; \+ member((mon,13), AllTimes)),
    % 周三
    (\+ member((wed,12), AllTimes) ; \+ member((wed,13), AllTimes)),
    % 周五
    (\+ member((fri,12), AllTimes) ; \+ member((fri,13), AllTimes)).

% 主谓词：生成符合所有约束的时间表
generate_timetable(Art, Dance, Music, Film) :-
    % 枚举各课程可选班次
    art(Art, ArtTimes),
    dance(Dance, DanceTimes),
    music(Music, MusicTimes),
    film(Film, FilmTimes),
    % 校验所有课程两两无时间冲突
    no_conflict(ArtTimes, DanceTimes),
    no_conflict(ArtTimes, MusicTimes),
    no_conflict(ArtTimes, FilmTimes),
    no_conflict(DanceTimes, MusicTimes),
    no_conflict(DanceTimes, FilmTimes),
    no_conflict(MusicTimes, FilmTimes),
    % 合并所有课程时间，校验午餐约束
    append([ArtTimes, DanceTimes, MusicTimes, FilmTimes], AllTimes),
    valid_lunch(AllTimes).

运行结果与常见坑点 #

在Prolog解释器中执行查询generate_timetable(A,D,M,F).，只会返回唯一合法解：

• 艺术课选MWF10班次
• 舞蹈课选周五1-4班次
• 音乐课选周一2点、周三2点、周五11点班次
• 电影课选周一noon、周三noon、周三3点班次

初学者写这道题最容易犯三个错误：

1. 时间表示不统一，比如混用"Friday noon"和fri12这类不同格式的标识，导致冲突判断漏判
2. 忘记舞蹈课占了周五13点（1点）时段，如果同时选了周五12点的电影班次，会直接占满周五两个可选午餐时段，违反约束
3. 冲突判断只校验部分课程组合，漏判比如音乐和电影的周三3点时段重叠问题

内容的提问来源于stack exchange，提问作者unmyelinated neuron