SWI-Prolog CLPFD的ins算子变量N报错 如何实现双向通用地图着色查询

问题描述 #

需用Prolog实现地图着色程序，使用的地图如下：

初始着色约束定义 #

colouring([A,B,C,D,E,F]) :- 
    maplist( #\=(A), [B,C,D,E] ),
    maplist( #\=(B), [C,D,F]),
    C #\= D,
    maplist( #\=(D), [E,F]),
    E #\= F.

其中[A,B,C,D,E,F]为取值范围1到N的颜色数字列表，要求求解器支持双向约束：输入6个颜色组成的列表L或自然数N时都可正常求解，通用查询regions_ncolors(L,N).也能正常返回结果。

已尝试实现及问题 #

版本1

regions_ncolors(L,N) :- colouring(L), L ins 1..N, label(L).

运行通用查询时ins算子不接受变量N，抛出参数未充分实例化错误。

版本2

int_cset_(N,Acc,Acc) :- N #= 0.
int_cset_(N,Acc,Cs) :- N_1 #= N-1, int_cset_(N_1,[N|Acc],Cs).
int_cset(N,Cs) :- int_cset_(N,[],Cs).

% 通用求解器
regions_ncolors(L,N) :- colouring(L), int_cset(N,Cs), subset(L,Cs), label(L).

存在问题：执行通用查询时对所有N仅返回同一个解，添加N的约束时会陷入无限循环。 #

问题核心是缺少对N的递增枚举逻辑，导致要么范围无法绑定，要么枚举顺序错误出现死循环。调整后的实现如下：

% 引入CLP(FD)约束库
:- use_module(library(clpfd)).

% 着色约束保持不变
colouring([A,B,C,D,E,F]) :- 
    maplist( #\=(A), [B,C,D,E] ),
    maplist( #\=(B), [C,D,F]),
    C #\= D,
    maplist( #\=(D), [E,F]),
    E #\= F.

regions_ncolors(L, N) :-
    % 固定颜色列表长度为6，适配6个区域的地图
    length(L, 6),
    % 约束N为正整数，避免非法值
    N #>= 1,
    % 从小到大递增枚举N，优先返回最小颜色数的解，避免死循环
    indomain(N),
    % 绑定颜色变量的取值范围
    L ins 1..N,
    % 应用相邻区域不同色的约束
    colouring(L),
    % 标签化输出具体着色结果
    label(L).

效果验证 #

• 通用查询regions_ncolors(L,N).：优先返回N=4（该地图最小着色数）的所有合法解，再依次返回N=5、N=6等更大N值的解，无死循环
• 指定N查询：如regions_ncolors(L,4).返回所有4色合法着色
• 指定L查询：如regions_ncolors([1,2,3,4,2,1], N).返回最小合法N=4，以及所有大于4的合法N值
• 合法性校验：如regions_ncolors([1,2,3,2,1,3], 3).正确返回false，符合3色无法满足该地图着色的结论

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