必须在 Prolog 中使用约束

Question

我目前正在尝试仅使用 clpfd 序言库提供的约束来解决这个难题 houses，这意味着我无法使用回溯！

基本上我想找出应该建造哪对房屋，以便所有连接之间只有 2 个距离。

我的输入是这样的坐标列表 [[0,0],[0,3],[2,0],[3,0],[2,1],[3,1],[2,2],[3,3]] 解决方案是：

[
   [[0,0],[0,3]],
   [[2,0],[3,1]],
   [[2,1],[3,0]],
   [[2,2],[3,3]]
]

我目前的进度是：

connect(Houses):-
    %There are only 2 distances and they're different
    length(Distances, 2),
    all_distinct(Distances),

    %One connection per 2 houses (pairs) means half the number of houses as connections
    length(Houses, NHouses),
    NConnections #= NHouses // 2,
    length(Connections, NConnections),

    restrictDistances(Connections, Distances), %restrict every connection to have one of the two distances


    %All the houses must be connected
    append(Connections, ConnectedHouses),
    ensureAllConnected(Houses, ConnectedHouses), %table

    removeSymmetries(Connections), %avoid symmetries

    %flatten list and labeling
    append(ConnectedHouses, HousesCoordinates),
    labeling([], HousesCoordinates),
    write(Connections).

/*
    All distances of all connections are one of the two distances
    Distance is kept squared to keep it an integer i.e. dist(connection) = dist([[x1, y1], [x2, y2]]) = (x2-x1)^2 + (y2-y1)^2
*/
restrictDistances([], _).
restrictDistances([[[X1, Y1], [X2, Y2]]|Connections], Distances):-
    DiffX #= X2 - X1,
    DiffY #= Y2 - Y1,
    Dis #= DiffX * DiffX + DiffY * DiffY,
    % element(Idx, Distances, Dis), %element
    member(Dis, Distances), %element
    restrictDistances(Connections, Distances).

/*
    Ensures all houses are connected
*/
ensureAllConnected([], _).
ensureAllConnected([H|Houses], ConnectedHouses):-
    member(H, ConnectedHouses),
    % element(_, ConnectedHouses, H),
    ensureAllConnected(Houses, ConnectedHouses).

/*
    Remove symmetries and connection permutations in final result
*/
removeSymmetries([_]).
removeSymmetries([[[X1, _], [X2, _]], [[X3, Y3], [X4, Y4]]|Connections]):-
    X1 #=< X2,
    X1 #=< X3,
    X3 #=< X4,
    removeSymmetries([[[X3, Y3], [X4, Y4]]|Connections]).

最糟糕的是此代码有效，但是不能使用谓词member，因为它使用了回溯...是的，谓词element 存在，但我无法用它替换，因为如果我替换第一个，输出是不同的，如果我替换第二个，我会得到一个实例化错误。

Answer 1

严格来说，这个问题是underspecified的，因为有不止一种距离，例如欧氏距离和哈密顿距离。显然，欧几里得距离是有意的，否则你会得到这个实例的多个解决方案。

对于这个难题，考虑哪些子任务可能使用全局约束进行编码是很有用的。这里有一些提示：

您需要找到匹配项 - 可以使用 assignment(Xs,Xs)。
您可以使用 table/2 对 (house,house,distance) 关系进行编码。
可以使用nvalue/2来约束不同距离的数量。

这些是 SICStus Prolog 中的全局约束。

必须在 Prolog 中使用约束

Obliged to use Constraints in Prolog

prolog

constraints

clpfd