Prolog生成满足XOR/字典序/辛积约束的0-1向量遇错误求助

API 探路者

2026-6-28

Prolog约束求解问题排查：0-1向量的XOR、字典序与辛积约束

我尝试生成6个长度为2N的0-1向量，需满足以下约束：

XOR操作约束
字典序约束
自定义辛积约束：若u = (u₁,...,u_N,u_{N+1},...,u_{2N})，v = (v₁,...,v_N,v_{N+1},...,v_{2N})，则σ(u,v) = (u₁v_N + u₂v_{N+1} + ... + u_Nv_{2N} + u_Nv₁ + ... + u_{2N}*v_N) mod 2

已知存在多组解，但添加3-4个约束后Prolog就返回false，以下是我的代码：

% Appel automatique à CLP(fd)
:- use_module(library(clpfd)).


% ordre lexicographique
leq([0],[1]).

leq([X|C1],[X|C2]):-
    leq(C1,C2).

leq([0|_],[1|_]).
    
% liste de listes de taille N
lengthliste([X],N):-
    length(X,N).
    
lengthliste([X|L],N):-
    length(X,N),
    lengthliste(L,N).
    


% xor

xor(0,0,0).
xor(1,0,1).
xor(0,1,1).
xor(1,1,0).

xorListe([X1],[X2],[X]):-
    !,xor(X1,X2,X).
    
xorListe([X1|L1],[X2|L2],[X|L]):-
    xor(X1,X2,X),
    xorListe(L1,L2,L),
    !.
    

% on calcule sigma(u,v) en faisant le produit scalaire entre u1,...,uN,uN+1,..U2N et vN+1,...,v2N,v1,...,vN

% on coupe L en un morceau de taille N et un autre
split(L,0,[],L).

split([X|Xs],N,[X|Ys],Zs) :- N1 is N - 1, split(Xs,N1,Ys,Zs).


% produit scalaire
ps([X1],[Y1],Res):-
    Res is X1*Y1.

ps([X1|L1],[X2|L2],Res):-
    ps(L1,L2,Res2),!,
    Res is xor(X1*X2, Res2).

% produit symplectique
sigma(O1,O2,N,Res):-
    split(O2,N,Moitie1,Moitie2),
    append(Moitie2,Moitie1,NewO2),
    ps(O1,NewO2,Res),!.
        




contraintes(O1,O2,O3,O4,O5,C, N):-
    NN is 2*N,
    length(O1,NN),
    length(O2,NN),
    length(O3,NN),
    length(O4,NN),
    length(O5,NN),
    length(C,NN),
    O1 ins {0,1},
    O2 ins {0,1},
    O3 ins {0,1},
    O4 ins {0,1},
    O5 ins {0,1},
    C ins {0,1},
    xorListeListe([O1,O2,O3,O4],O5),
    xorListe(C,O1,D1),
    xorListe(C,O2,D2),
    xorListe(C,O3,D3),
    xorListe(D3,O5,D4),
    xorListe(D3,O4,D5),
    xorListe(D2,O4,D6),
    xorListe(D2,O5,D7),
    xorListe(D1,O4,D8),
    xorListe(D1,O5,D9),
    leq(O1, C),
    leq(O1, O2),
    leq(O2, O3),
    leq(O3, O4),
    leq(O4, O5),
    leq(O1,D1),
    leq(O2,D2),
    leq(O2,D3),
    leq(O1,D4),
    leq(O1,D5),
    leq(O1,D6),
    leq(O1,D7),
    leq(O2,D8),
    leq(O2,D9),
    sigma(O1,O2,N,1),
    sigma(O1,O3,N,1),
    sigma(O1,O4,N,1),
    sigma(O1,O5,N,1),
    sigma(O2,O3,N,1),
    sigma(O2,O4,N,1),
    sigma(O2,O5,N,1),
    sigma(O3,O4,N,1),
    sigma(O3,O5,N,1),
    sigma(O4,O5,N,1),
    sigma(O4,C,N,1),
    sigma(O1,C,N,0),
    sigma(O2,C,N,0),
    sigma(O3,C,N,0),
    labeling([],[O1,O2,O3,O4,O5,C]).

核心问题排查与修正

1. 缺失关键谓词实现

代码中调用了xorListeListe([O1,O2,O3,O4],O5)但未实现该谓词，直接导致调用失败返回false。需要补充多列表逐元素异或的逻辑：

xorListeListe([O], O).
xorListeListe([L|Ls], O) :-
    xorListeListe(Ls, Temp),
    xorListe(L, Temp, O).

2. 辛积计算逻辑错误

辛积要求的是模2和，但当前ps谓词用xor递归累加，且使用is进行即时数值计算——这会导致变量未绑定时直接报错，同时无法利用CLP(fd)的约束传播能力。修正为CLP(fd)兼容的模2点积：

% 模2点积：Res = sum(Xi*Yi) mod 2
ps([], [], 0).
ps([X|Xs], [Y|Ys], Res) :-
    ps(Xs, Ys, Res0),
    Res #= (X*Y + Res0) mod 2.

3. 字典序谓词逻辑缺陷

当前leq缺少空列表的基础情况（空列表字典序相等），且存在冗余规则。修正为严谨的递归逻辑：

leq([], []).
leq([0|_], [1|_]).
leq([X|C1], [X|C2]) :- leq(C1, C2).

4. 即时计算与CLP(fd)约束冲突

所有涉及变量的计算都应使用CLP(fd)的约束操作符（如#=）替代is，确保约束能被系统传播，而非直接进行数值计算。

5. 搜索效率优化

调整labeling策略为[ff]（首次失败），优先绑定域最小的变量，减少搜索空间：

labeling([ff], [O1,O2,O3,O4,O5,C]).

修正后的完整代码

:- use_module(library(clpfd)).

% 字典序小于等于：A ≤ B（0-1向量）
leq([], []).
leq([0|_], [1|_]).
leq([X|C1], [X|C2]) :- leq(C1, C2).

% 两列表逐元素XOR
xorListe([], [], []).
xorListe([X|Xs], [Y|Ys], [Z|Zs]) :-
    Z #= X xor Y,
    xorListe(Xs, Ys, Zs).

% 多列表逐元素XOR（O是所有输入列表的逐元素异或结果）
xorListeListe([O], O).
xorListeListe([L|Ls], O) :-
    xorListeListe(Ls, Temp),
    xorListe(L, Temp, O).

% 拆分列表为前N个和剩余部分
split(L, N, Front, Back) :-
    length(Front, N),
    append(Front, Back, L).

% 模2点积：Res = sum(Xi*Yi) mod 2
ps([], [], 0).
ps([X|Xs], [Y|Ys], Res) :-
    ps(Xs, Ys, Res0),
    Res #= (X*Y + Res0) mod 2.

% 辛积计算
sigma(O1, O2, N, Res) :-
    split(O2, N, Moitie1, Moitie2),
    append(Moitie2, Moitie1, NewO2),
    ps(O1, NewO2, Res).

contraintes(O1, O2, O3, O4, O5, C, N) :-
    NN is 2*N,
    % 声明所有向量长度和域
    maplist(length, [O1,O2,O3,O4,O5,C], [NN,NN,NN,NN,NN,NN]),
    maplist(ins 0..1, [O1,O2,O3,O4,O5,C]),
    
    % XOR约束
    xorListeListe([O1,O2,O3,O4], O5),
    xorListe(C, O1, D1),
    xorListe(C, O2, D2),
    xorListe(C, O3, D3),
    xorListe(D3, O5, D4),
    xorListe(D3, O4, D5),
    xorListe(D2, O4, D6),
    xorListe(D2, O5, D7),
    xorListe(D1, O4, D8),
    xorListe(D1, O5, D9),
    
    % 字典序约束
    leq(O1, C),
    leq(O1, O2),
    leq(O2, O3),
    leq(O3, O4),
    leq(O4, O5),
    leq(O1, D1),
    leq(O2, D2),
    leq(O2, D3),
    leq(O1, D4),
    leq(O1, D5),
    leq(O1, D6),
    leq(O1, D7),
    leq(O2, D8),
    leq(O2, D9),
    
    % 辛积约束
    sigma(O1, O2, N, 1),
    sigma(O1, O3, N, 1),
    sigma(O1, O4, N, 1),
    sigma(O1, O5, N, 1),
    sigma(O2, O3, N, 1),
    sigma(O2, O4, N, 1),
    sigma(O2, O5, N, 1),
    sigma(O3, O4, N, 1),
    sigma(O3, O5, N, 1),
    sigma(O4, O5, N, 1),
    sigma(O4, C, N, 1),
    sigma(O1, C, N, 0),
    sigma(O2, C, N, 0),
    sigma(O3, C, N, 0),
    
    % 标签化，使用首次失败策略优化搜索
    labeling([ff], [O1,O2,O3,O4,O5,C]).

内容的提问来源于stack exchange，提问作者Arnaud Bégyn

Prolog生成满足XOR/字典序/辛积约束的0-1向量遇错误求助

核心问题排查与修正 #

1. 缺失关键谓词实现 #

2. 辛积计算逻辑错误 #

3. 字典序谓词逻辑缺陷 #

4. 即时计算与CLP(fd)约束冲突 #

5. 搜索效率优化 #

修正后的完整代码 #