使用 Prolog 优化约束逻辑编程中的寻路
我正在开发一个小型序言应用程序来解决摩天大楼和栅栏 谜题。
未解决的谜题：
已解决的谜题：
当我通过该程序时，已经解决了谜题，它很快，几乎是瞬时的，为我验证它。当我通过程序解决非常小的难题时（例如，2x2，当然，修改了规则），找到解决方案的速度也相当快。
问题在于计算“原始”尺寸为 6x6 的谜题。我让它运行了 5 个小时左右才中止它。时间太多了。
我发现耗时最长的部分是“栅栏”，而不是“摩天大楼”。单独运行“摩天大楼”会产生快速解决方案。
这是我的栅栏算法：
- 顶点由数字表示，0 表示路径不经过该特定顶点，> > 1 表示该顶点在路径中的顺序。
- 限制每个单元格周围有适当数量的线条。
- 这意味着如果两个顶点具有连续编号，则它们是连接的，例如 1 -> 。 2, 2-> 1, 1 -> 1
最大，最大-> 1（Max是路径中最后一个顶点的编号。通过maximum/2计算）
- 这意味着如果两个顶点具有连续编号，则它们是连接的，例如 1 -> 。 2, 2-> 1, 1 -> 1
- 确保每个非零顶点至少有两个具有连续编号的相邻顶点
- 将
Max约束为等于(BoardWidth + 1)^2 - NumberOfZeros（BoardWidth+1是沿边的顶点数，NumberOfZeros通过count/4计算）。 - 使用
nvalue(Vertices, Max + 1)确保Vertices中不同值的数量为Max（即路径）加上1（零值） - 找到第一个包含
3的单元格，并强制路径从此处开始和结束，以提高效率
我可以采取哪些措施来提高效率？下面包含代码以供参考。
skyscrapersinfences.pro
:-use_module(library(clpfd)).
:-use_module(library(lists)).
:-ensure_loaded('utils.pro').
:-ensure_loaded('s1.pro').
print_row([]).
print_row([Head|Tail]) :-
write(Head), write(' '),
print_row(Tail).
print_board(Board, BoardWidth) :-
print_board(Board, BoardWidth, 0).
print_board(_, BoardWidth, BoardWidth).
print_board(Board, BoardWidth, Index) :-
make_segment(Board, BoardWidth, Index, row, Row),
print_row(Row), nl,
NewIndex is Index + 1,
print_board(Board, BoardWidth, NewIndex).
print_boards([], _).
print_boards([Head|Tail], BoardWidth) :-
print_board(Head, BoardWidth), nl,
print_boards(Tail, BoardWidth).
get_board_element(Board, BoardWidth, X, Y, Element) :-
Index is BoardWidth*Y + X,
get_element_at(Board, Index, Element).
make_column([], _, _, []).
make_column(Board, BoardWidth, Index, Segment) :-
get_element_at(Board, Index, Element),
munch(Board, BoardWidth, MunchedBoard),
make_column(MunchedBoard, BoardWidth, Index, ColumnTail),
append([Element], ColumnTail, Segment).
make_segment(Board, BoardWidth, Index, row, Segment) :-
NIrrelevantElements is BoardWidth*Index,
munch(Board, NIrrelevantElements, MunchedBoard),
select_n_elements(MunchedBoard, BoardWidth, Segment).
make_segment(Board, BoardWidth, Index, column, Segment) :-
make_column(Board, BoardWidth, Index, Segment).
verify_segment(_, 0).
verify_segment(Segment, Value) :-
verify_segment(Segment, Value, 0).
verify_segment([], 0, _).
verify_segment([Head|Tail], Value, Max) :-
Head #> Max #<=> B,
Value #= M+B,
maximum(NewMax, [Head, Max]),
verify_segment(Tail, M, NewMax).
exactly(_, [], 0).
exactly(X, [Y|L], N) :-
X #= Y #<=> B,
N #= M +B,
exactly(X, L, M).
constrain_numbers(Vars) :-
exactly(3, Vars, 1),
exactly(2, Vars, 1),
exactly(1, Vars, 1).
iteration_values(BoardWidth, Index, row, 0, column) :-
Index is BoardWidth - 1.
iteration_values(BoardWidth, Index, Type, NewIndex, Type) :-
\+((Type = row, Index is BoardWidth - 1)),
NewIndex is Index + 1.
solve_skyscrapers(Board, BoardWidth) :-
solve_skyscrapers(Board, BoardWidth, 0, row).
solve_skyscrapers(_, BoardWidth, BoardWidth, column).
solve_skyscrapers(Board, BoardWidth, Index, Type) :-
make_segment(Board, BoardWidth, Index, Type, Segment),
domain(Segment, 0, 3),
constrain_numbers(Segment),
observer(Type, Index, forward, ForwardObserver),
verify_segment(Segment, ForwardObserver),
observer(Type, Index, reverse, ReverseObserver),
reverse(Segment, ReversedSegment),
verify_segment(ReversedSegment, ReverseObserver),
iteration_values(BoardWidth, Index, Type, NewIndex, NewType),
solve_skyscrapers(Board, BoardWidth, NewIndex, NewType).
build_vertex_list(_, Vertices, BoardWidth, X, Y, List) :-
V1X is X, V1Y is Y, V1Index is V1X + V1Y*(BoardWidth+1),
V2X is X+1, V2Y is Y, V2Index is V2X + V2Y*(BoardWidth+1),
V3X is X+1, V3Y is Y+1, V3Index is V3X + V3Y*(BoardWidth+1),
V4X is X, V4Y is Y+1, V4Index is V4X + V4Y*(BoardWidth+1),
get_element_at(Vertices, V1Index, V1),
get_element_at(Vertices, V2Index, V2),
get_element_at(Vertices, V3Index, V3),
get_element_at(Vertices, V4Index, V4),
List = [V1, V2, V3, V4].
build_neighbors_list(Vertices, VertexWidth, X, Y, [NorthMask, EastMask, SouthMask, WestMask], [NorthNeighbor, EastNeighbor, SouthNeighbor, WestNeighbor]) :-
NorthY is Y - 1,
EastX is X + 1,
SouthY is Y + 1,
WestX is X - 1,
NorthNeighborIndex is (NorthY)*VertexWidth + X,
EastNeighborIndex is Y*VertexWidth + EastX,
SouthNeighborIndex is (SouthY)*VertexWidth + X,
WestNeighborIndex is Y*VertexWidth + WestX,
(NorthY >= 0, get_element_at(Vertices, NorthNeighborIndex, NorthNeighbor) -> NorthMask = 1 ; NorthMask = 0),
(EastX < VertexWidth, get_element_at(Vertices, EastNeighborIndex, EastNeighbor) -> EastMask = 1 ; EastMask = 0),
(SouthY < VertexWidth, get_element_at(Vertices, SouthNeighborIndex, SouthNeighbor) -> SouthMask = 1 ; SouthMask = 0),
(WestX >= 0, get_element_at(Vertices, WestNeighborIndex, WestNeighbor) -> WestMask = 1 ; WestMask = 0).
solve_path(_, VertexWidth, 0, VertexWidth) :-
write('end'),nl.
solve_path(Vertices, VertexWidth, VertexWidth, Y) :-
write('switch row'),nl,
Y \= VertexWidth,
NewY is Y + 1,
solve_path(Vertices, VertexWidth, 0, NewY).
solve_path(Vertices, VertexWidth, X, Y) :-
X >= 0, X < VertexWidth, Y >= 0, Y < VertexWidth,
write('Path: '), nl,
write('Vertex width: '), write(VertexWidth), nl,
write('X: '), write(X), write(' Y: '), write(Y), nl,
VertexIndex is X + Y*VertexWidth,
write('1'),nl,
get_element_at(Vertices, VertexIndex, Vertex),
write('2'),nl,
build_neighbors_list(Vertices, VertexWidth, X, Y, [NorthMask, EastMask, SouthMask, WestMask], [NorthNeighbor, EastNeighbor, SouthNeighbor, WestNeighbor]),
L1 = [NorthMask, EastMask, SouthMask, WestMask],
L2 = [NorthNeighbor, EastNeighbor, SouthNeighbor, WestNeighbor],
write(L1),nl,
write(L2),nl,
write('3'),nl,
maximum(Max, Vertices),
write('4'),nl,
write('Max: '), write(Max),nl,
write('Vertex: '), write(Vertex),nl,
(Vertex #> 1 #/\ Vertex #\= Max) #=> (
((NorthMask #> 0 #/\ NorthNeighbor #> 0) #/\ (NorthNeighbor #= Vertex - 1)) #\
((EastMask #> 0 #/\ EastNeighbor #> 0) #/\ (EastNeighbor #= Vertex - 1)) #\
((SouthMask #> 0 #/\ SouthNeighbor #> 0) #/\ (SouthNeighbor #= Vertex - 1)) #\
((WestMask #> 0 #/\ WestNeighbor #> 0) #/\ (WestNeighbor #= Vertex - 1))
) #/\ (
((NorthMask #> 0 #/\ NorthNeighbor #> 0) #/\ (NorthNeighbor #= Vertex + 1)) #\
((EastMask #> 0 #/\ EastNeighbor #> 0) #/\ (EastNeighbor #= Vertex + 1)) #\
((SouthMask #> 0 #/\ SouthNeighbor #> 0) #/\ (SouthNeighbor #= Vertex + 1)) #\
((WestMask #> 0 #/\ WestNeighbor #> 0) #/\ (WestNeighbor #= Vertex + 1))
),
write('5'),nl,
Vertex #= 1 #=> (
((NorthMask #> 0 #/\ NorthNeighbor #> 0) #/\ (NorthNeighbor #= Max)) #\
((EastMask #> 0 #/\ EastNeighbor #> 0) #/\ (EastNeighbor #= Max)) #\
((SouthMask #> 0 #/\ SouthNeighbor #> 0) #/\ (SouthNeighbor #= Max)) #\
((WestMask #> 0 #/\ WestNeighbor #> 0) #/\ (WestNeighbor #= Max))
) #/\ (
((NorthMask #> 0 #/\ NorthNeighbor #> 0) #/\ (NorthNeighbor #= 2)) #\
((EastMask #> 0 #/\ EastNeighbor #> 0) #/\ (EastNeighbor #= 2)) #\
((SouthMask #> 0 #/\ SouthNeighbor #> 0) #/\ (SouthNeighbor #= 2)) #\
((WestMask #> 0 #/\ WestNeighbor #> 0) #/\ (WestNeighbor #= 2))
),
write('6'),nl,
Vertex #= Max #=> (
((NorthMask #> 0 #/\ NorthNeighbor #> 0) #/\ (NorthNeighbor #= 1)) #\
((EastMask #> 0 #/\ EastNeighbor #> 0) #/\ (EastNeighbor #= 1)) #\
((SouthMask #> 0 #/\ SouthNeighbor #> 0) #/\ (SouthNeighbor #= 1)) #\
((WestMask #> 0 #/\ WestNeighbor #> 0) #/\ (WestNeighbor #= 1))
) #/\ (
((NorthMask #> 0 #/\ NorthNeighbor #> 0) #/\ (NorthNeighbor #= Max - 1)) #\
((EastMask #> 0 #/\ EastNeighbor #> 0) #/\ (EastNeighbor #= Max - 1)) #\
((SouthMask #> 0 #/\ SouthNeighbor #> 0) #/\ (SouthNeighbor #= Max - 1)) #\
((WestMask #> 0 #/\ WestNeighbor #> 0) #/\ (WestNeighbor #= Max - 1))
),
write('7'),nl,
NewX is X + 1,
solve_path(Vertices, VertexWidth, NewX, Y).
solve_fences(Board, Vertices, BoardWidth) :-
VertexWidth is BoardWidth + 1,
write('- Solving vertices'),nl,
solve_vertices(Board, Vertices, BoardWidth, 0, 0),
write('- Solving path'),nl,
solve_path(Vertices, VertexWidth, 0, 0).
solve_vertices(_, _, BoardWidth, 0, BoardWidth).
solve_vertices(Board, Vertices, BoardWidth, BoardWidth, Y) :-
Y \= BoardWidth,
NewY is Y + 1,
solve_vertices(Board, Vertices, BoardWidth, 0, NewY).
solve_vertices(Board, Vertices, BoardWidth, X, Y) :-
X >= 0, X < BoardWidth, Y >= 0, Y < BoardWidth,
write('process'),nl,
write('X: '), write(X), write(' Y: '), write(Y), nl,
build_vertex_list(Board, Vertices, BoardWidth, X, Y, [V1, V2, V3, V4]),
write('1'),nl,
get_board_element(Board, BoardWidth, X, Y, Element),
write('2'),nl,
maximum(Max, Vertices),
(V1 #> 0 #/\ V2 #> 0 #/\
(
(V1 + 1 #= V2) #\
(V1 - 1 #= V2) #\
(V1 #= Max #/\ V2 #= 1) #\
(V1 #= 1 #/\ V2 #= Max)
)
) #<=> B1,
(V2 #> 0 #/\ V3 #> 0 #/\
(
(V2 + 1 #= V3) #\
(V2 - 1 #= V3) #\
(V2 #= Max #/\ V3 #= 1) #\
(V2 #= 1 #/\ V3 #= Max)
)
) #<=> B2,
(V3 #> 0 #/\ V4 #> 0 #/\
(
(V3 + 1 #= V4) #\
(V3 - 1 #= V4) #\
(V3 #= Max #/\ V4 #= 1) #\
(V3 #= 1 #/\ V4 #= Max)
)
) #<=> B3,
(V4 #> 0 #/\ V1 #> 0 #/\
(
(V4 + 1 #= V1) #\
(V4 - 1 #= V1) #\
(V4 #= Max #/\ V1 #= 1) #\
(V4 #= 1 #/\ V1 #= Max)
)
) #<=> B4,
write('3'),nl,
sum([B1, B2, B3, B4], #= , C),
write('4'),nl,
Element #> 0 #=> C #= Element,
write('5'),nl,
NewX is X + 1,
solve_vertices(Board, Vertices, BoardWidth, NewX, Y).
sel_next_variable_for_path(Vars,Sel,Rest) :-
% write(Vars), nl,
findall(Idx-Cost, (nth1(Idx, Vars,V), fd_set(V,S), fdset_size(S,Size), fdset_min(S,Min), var_cost(Min,Size, Cost)), L),
min_member(comp, BestIdx-_MinCost, L),
nth1(BestIdx, Vars, Sel, Rest),!.
var_cost(0, _, 1000000) :- !.
var_cost(_, 1, 1000000) :- !.
var_cost(X, _, X).
%build_vertex_list(_, Vertices, BoardWidth, X, Y, List)
constrain_starting_and_ending_vertices(Vertices, [V1,V2,V3,V4]) :-
maximum(Max, Vertices),
(V1 #= 1 #/\ V2 #= Max #/\ V3 #= Max - 1 #/\ V4 #= 2 ) #\
(V1 #= Max #/\ V2 #= 1 #/\ V3 #= 2 #/\ V4 #= Max - 1 ) #\
(V1 #= Max - 1 #/\ V2 #= Max #/\ V3 #= 1 #/\ V4 #= 2 ) #\
(V1 #= 2 #/\ V2 #= 1 #/\ V3 #= Max #/\ V4 #= Max - 1 ) #\
(V1 #= 1 #/\ V2 #= 2 #/\ V3 #= Max - 1 #/\ V4 #= Max ) #\
(V1 #= Max #/\ V2 #= Max - 1 #/\ V3 #= 2 #/\ V4 #= 1 ) #\
(V1 #= Max - 1 #/\ V2 #= 2 #/\ V3 #= 1 #/\ V4 #= Max ) #\
(V1 #= 2 #/\ V2 #= Max - 1 #/\ V3 #= Max #/\ V4 #= 1 ).
set_starting_and_ending_vertices(Board, Vertices, BoardWidth) :-
set_starting_and_ending_vertices(Board, Vertices, BoardWidth, 0, 0).
set_starting_and_ending_vertices(Board, Vertices, BoardWidth, BoardWidth, Y) :-
Y \= BoardWidth,
NewY is Y + 1,
solve_path(Board, Vertices, BoardWidth, 0, NewY).
set_starting_and_ending_vertices(Board, Vertices, BoardWidth, X, Y) :-
X >= 0, X < BoardWidth, Y >= 0, Y < BoardWidth,
build_vertex_list(_, Vertices, BoardWidth, X, Y, List),
get_board_element(Board, BoardWidth, X, Y, Element),
(Element = 3 ->
constrain_starting_and_ending_vertices(Vertices, List)
;
NewX is X + 1,
set_starting_and_ending_vertices(Board, Vertices, BoardWidth, NewX, Y)).
solve(Board, Vertices, BoardWidth) :-
write('Skyscrapers'), nl,
solve_skyscrapers(Board, BoardWidth),
write('Labeling'), nl,
labeling([ff], Board), !,
write('Setting domain'), nl,
NVertices is (BoardWidth+1)*(BoardWidth+1),
domain(Vertices, 0, NVertices),
write('Starting and ending vertices'), nl,
set_starting_and_ending_vertices(Board, Vertices, BoardWidth),
write('Setting maximum'), nl,
maximum(Max, Vertices),
write('1'),nl,
Max #> BoardWidth + 1,
write('2'),nl,
Max #< NVertices,
count(0, Vertices, #=, NZeros),
Max #= NVertices - NZeros,
write('3'),nl,
write('Calling nvalue'), nl,
ValueCount #= Max + 1,
nvalue(ValueCount, Vertices),
write('Solving fences'), nl,
solve_fences(Board, Vertices, BoardWidth),
write('Labeling'), nl,
labeling([ff], Vertices).
main :-
board(Board),
board_width(BoardWidth),
vertices(Vertices),
solve(Board, Vertices, BoardWidth),
%findall(Board,
% labeling([ff], Board),
% Boards
%),
%append(Board, Vertices, Final),
write('done.'),nl,
print_board(Board, 6), nl,
print_board(Vertices, 7).
utils.pro
get_element_at([Head|_], 0, Head).
get_element_at([_|Tail], Index, Element) :-
Index \= 0,
NewIndex is Index - 1,
get_element_at(Tail, NewIndex, Element).
reverse([], []).
reverse([Head|Tail], Inv) :-
reverse(Tail, Aux),
append(Aux, [Head], Inv).
munch(List, 0, List).
munch([_|Tail], Count, FinalList) :-
Count > 0,
NewCount is Count - 1,
munch(Tail, NewCount, FinalList).
select_n_elements(_, 0, []).
select_n_elements([Head|Tail], Count, FinalList) :-
Count > 0,
NewCount is Count - 1,
select_n_elements(Tail, NewCount, Result),
append([Head], Result, FinalList).
generate_list(Element, NElements, [Element|Result]) :-
NElements > 0,
NewNElements is NElements - 1,
generate_list(Element, NewNElements, Result).
generate_list(_, 0, []).
s1.pro
% Skyscrapers and Fences puzzle S1
board_width(6).
%observer(Type, Index, Orientation, Observer),
observer(row, 0, forward, 2).
observer(row, 1, forward, 2).
observer(row, 2, forward, 2).
observer(row, 3, forward, 1).
observer(row, 4, forward, 2).
observer(row, 5, forward, 1).
observer(row, 0, reverse, 1).
observer(row, 1, reverse, 1).
observer(row, 2, reverse, 2).
observer(row, 3, reverse, 3).
observer(row, 4, reverse, 2).
observer(row, 5, reverse, 2).
observer(column, 0, forward, 2).
observer(column, 1, forward, 3).
observer(column, 2, forward, 0).
observer(column, 3, forward, 2).
observer(column, 4, forward, 2).
observer(column, 5, forward, 1).
observer(column, 0, reverse, 1).
observer(column, 1, reverse, 1).
observer(column, 2, reverse, 2).
observer(column, 3, reverse, 2).
observer(column, 4, reverse, 2).
observer(column, 5, reverse, 2).
board(
[
_, _, 2, _, _, _,
_, _, _, _, _, _,
_, 2, _, _, _, _,
_, _, _, 2, _, _,
_, _, _, _, _, _,
_, _, _, _, _, _
]
).
vertices(
[
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _
]
).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我也像tinterer一样喜欢这个谜题。但作为一名校长，我首先必须为摩天大楼和栅栏部分找到合适的策略，然后对后者进行深入调试，导致复制变量问题，导致我锁定了好几个小时。
一旦解决了这个错误，我就面临着第一次尝试的低效率。我在普通的 Prolog 中重新设计了一个类似的模式，只是为了验证它的效率有多低。
至少，我了解如何更有效地使用 CLP(FD) 来模拟问题（在 twinterer 答案的帮助下），现在程序速度很快（0,2 秒）。所以现在我可以提示您有关您的代码的信息：所需的约束比您编码的约束远简单：对于栅栏部分，即建筑物位置固定，我们有 2 个约束：高度的边数> 0，并将边连接在一起：当使用边时，相邻边的总和必须为1（两边）。
这是我的代码的最后一个版本，使用 SWI-Prolog 开发。
输出：
正如我所提到的，我的第一次尝试更加“程序化”：它绘制了一个循环，但我无法解决的问题基本上是顶点子集的基数必须事先已知，基于全局约束 全部不同。它在缩小的 4*4 拼图上运行得很痛苦，但在 6*6 原始拼图上几个小时后我停止了它。不管怎样，从头开始学习如何用 CLP(FD) 绘制路径是有回报的。
谢谢你提出这么有趣的问题。
更多编辑：这里是完整解决方案的主要缺失代码段（index_square.pl）
I also, like twinterer, enjoyed this puzzle. But being a principiant, I had first to discover an appropriate strategy, for both skyscrapes and fences part, and then deeply debugging the latter, cause a copy variables problem that locked me many hours.
Once solved the bug, I faced the inefficiency of my first attempt. I reworked in plain Prolog a similar schema, just to verify how inefficient it was.
At least, I understood how use CLP(FD) more effectively to model the problem (with help from the twinterer' answer), and now the program is fast (0,2 sec). So now I can hint you about your code: the required constraints are far simpler than those you coded: for the fences part, i.e. with a buildings placement fixed, we have 2 constraints: number of edges where height > 0, and linking the edges together: when an edge is used, the sum of adjacents must be 1 (on both sides).
Here is the last version of my code, developed with SWI-Prolog.
The output:
As I mentioned, my first attempt was more 'procedural': it draws a loop, but the problem I was unable to solve is basically that the cardinality of vertices subset must be known before, being based on the global constraint all_different. It painfully works on a reduced 4*4 puzzle, but I stopped it after some hours on the 6*6 original. Anyway, learning from scratch how to draw a path with CLP(FD) has been rewarding.
Thanks you for such interesting question.
MORE EDIT:here the main miss piece of code for the complete solution (index_square.pl)
快速浏览一下您的程序就会发现您大量使用了具体化。不幸的是，这样的表述意味着 SICStus 等当前系统的一致性较弱。
然而，通常可以将事物表述得更紧凑，从而获得更好的一致性。这是一个示例，您可以根据自己的需要进行调整。
假设您想要表达 (X1,Y1) 和 (X2,Y2) 是水平或垂直邻居。您可以对每种可能性说
( X1+1 #= X2 #/\ Y1 #= Y2 ) #\ ...（并检查您的健康保险是否涵盖 RSI）。或者您可以说
abs(X1-X2)+abs(Y1-Y2) #= 1。在过去，SICStus Prolog 曾经为此有一个对称差异(--)/2，但我假设您使用的是版本 4。上面的公式保持了间隔一致性（至少我从我尝试过的例子）：
所以
X2很容易受到约束！在某些情况下（正如您在回复中所指出的），您可能需要具体化形式来维护其他约束。在这种情况下，您可以考虑同时发布。
翻阅手册，有几个可能也很有趣的组合约束。作为快速修复，
smt/1可能会有所帮助（4.2.0 中的新增功能）。有兴趣了解这一点...另一种可能性可能是使用另一种实现：例如 YAP 的
library(clpfd)或 SWI。A quick glance over your program suggests that you use reification quite heavily. Unfortunately, such formulations imply weak consistency in current systems like SICStus.
Often, however, things can be formulated more compactly leading to better consistency. Here is one example which you might adapt to your needs.
Say, you want to express that (X1,Y1) and (X2,Y2) are horizontal or vertical neighbors. You could say
( X1+1 #= X2 #/\ Y1 #= Y2 ) #\ ...for each possiblity (and check if your health insurance covers RSI).Or you can say
abs(X1-X2)+abs(Y1-Y2) #= 1. In the olden tymes SICStus Prolog used to have a symmetric difference(--)/2for that, but I assume you are using version 4.Above formulation maintains interval consistency (at least I conclude this from the examples I tried):
So the
X2is readily constrained!There might be situations (as you indicate in your response) where you need the reified form to maintain other constraints. In this case you might consider to post both.
Leaf through the manual, there are several combinatorial constraints that might be interesting too. And as a quick fix,
smt/1might help (new in 4.2.0). Would be interested to hear about this...Another possibility might be to use another implementation: For example
library(clpfd)of YAP or SWI.多么漂亮的小拼图啊！为了理解这些属性，我在 ECLiPSe 中实现了一个解决方案。可以在这里找到它： http://pastebin.com/eZbgjgFA （如果您看到循环，请不要担心代码：这些可以很容易地翻译成标准的 Prolog 谓词，但是，还有其他东西，从 ECLiPSe 翻译成 Sicstus 并不那么容易）
执行时间比您报告的要快，但可能会。更好：
您在答案中看到的是边矩阵。每个内部术语表示拼图中的一个字段，哪个边是活动的（左、上、右、下）。我把剩下的删掉了。
我总共使用了八个数组：HxWx4 边数组 (0/1)、每个字段顶点的活动边 (H+1)x(W+1) 数组 (0/2)、活动边总和的 HxW 数组边 (0..3)、建筑物的 HxW 数组 (0/1)、建筑物高度的两个 [H,W]x3 数组以及建筑物位置的两个 [H,W]x3 数组。
必须只有一条路径的要求并不作为约束，而只是在标记过程中找到潜在解决方案后作为检查执行。
约束是：
总和数组必须包含每个字段的该字段的活动边的总和
接触边相邻字段的接触边必须包含相同的值
顶点必须有两个活动边连接到它们，或者没有
必须放置三座建筑物。一些建筑物是根据拼图的定义放置
行/列中的每个建筑物高度必须不同
建筑物高度对应于该位置的活动边的总和
可见建筑物的数量由拼图的定义指定。这限制了建筑物在行/列中出现的顺序。
建筑物在行/列中的位置必须按升序给出
一旦第一个/第二个位置/第三个建筑物已知，我们可以推断出一些不能放置建筑物的位置。
有了这组约束，我们现在就可以进行标记了。标记分两步完成，这加快了求解过程。
第一步，仅标记建筑物位置。这是最受限制的部分，如果我们在这里找到解决方案，那么剩下的就容易多了。
在第二步中，所有其他变量都被标记。对于这两个步骤，我都选择“先失败”作为标记策略，即首先标记具有最小域的变量。
如果不先解决建筑位置，程序就会花费更长的时间（我总是在几分钟后停止它）。由于我没有第二个可用的谜题实例，因此我不确定搜索策略在所有实例中都可行，尽管
再次查看您的程序，您似乎遵循了类似的策略，即首先放置建筑物。但是，您可以在设置约束和标签之间进行迭代。这效率不高。在 CLP 中，您应该始终预先放置约束（除非约束确实取决于部分解决方案的当前状态），并且仅当发布约束时您才搜索解决方案。这样，您可以在搜索过程中检测到所有约束的失败。否则，您可能会找到一个满足您迄今为止发布的约束集的部分解决方案，却发现一旦添加其他约束就无法完成该解决方案。
另外，如果您有不同的变量集，请试验变量的标记顺序。不过，这并没有通用的方法。
希望这有帮助！
What a nice little puzzle! In order to understand the properties, I implemented a solution in ECLiPSe. It can be found here: http://pastebin.com/eZbgjgFA (Don't worry if you see loops in the code: these can be easily translated into standard Prolog predicates. There's other stuff, though, that's not so easily translated from ECLiPSe into Sicstus)
Execution time is faster than what you report, but could probably be better:
What you see in the answer is the matrix of edges. Each inner term denotes for a field in the puzzle, which edge is active (left,up,right,down). I edited out the rest.
I used eight arrays in total: the HxWx4 array of edges (0/1), a (H+1)x(W+1) array of active edges per field vertex (0/2), a HxW array of sums of active edges (0..3), a HxW array of buildings (0/1), two [H,W]x3 arrays of building heights, and two [H,W]x3 arrays of building positions.
The requirement that there must be only one path is not put as a constraint, but merely executed as a check after a potential solution is found during labeling.
The constraints are:
the sum array must contain for each field the sum of the active edges for that field
touching edges of neighbouring fields must contain the same value
the vertex points must have two active edges connected to them, or none
in each column/row, exactly three buildings must be placed. Some of the buildings are placed by the definition of the puzzle
each building height in a row/column must be different
the building height corresponds to the sum of active edges at this position
the number of visible buildings is specified by the definition of the puzzle. This restricts the order in which the buildings can appear in the row/column.
the positions of the buildings in a row/column must be given in ascending order
once the position of the first/second/third building is known, we can infer some positions where no building can be placed.
With this set of constraints, we are now ready to label. Labeling is done in two steps, which speeds up the solving process.
In a first step, only the building positions are labeled. This is the most restricted part, and if we find a solution here, the rest is much easier.
In the second step, all other variables are labeled. For both steps, I chose "first fail" as labeling strategy, i.e., label variables with smallest domain first.
Without solving the building positions first, the program takes much longer (I always stopped it after some minutes). Since I didn't have a second puzzle instance available, I'm not sure that the search strategy will feasible in all instances, though
Looking through your program again, it seems that you follow a similar strategy of placing the buildings first. However, you iterate between setting constraints and labeling. This is not efficient. In CLP, you should always place the constraints upfront (unless the constraints really depend on the current state of the partial solution), and only when the constraints are posted you search for a solution. This way, you can detect failure regarding all constraints during your search. Otherwise, you may find a partial solution that fulfils the set of constraints that you posted so far, only to find out that you cannot complete the solution once the other constraints are added.
Also, if you have different sets of variables, experiment with the order in which the variables are labeled. There's no universal recipe for that, though.
Hope this helps!