prolog中的无限循环？还是只是很慢？

Question

我试图弄清楚我的Prolog程序中是否有无限循环,或者如果我写的不好,所以它很慢.我正在尝试解决dailyprogrammer subreddit中的平方和链问题.给定数字N,找到数字1-N(包括)的排序,使得排序中的每对相邻数字的总和是完美的正方形.这个最小的N是15,具有排序[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9].这是我试图用来解决问题的代码:

is_square(Num):- is_square_help(Num, 0).

is_square_help(Num, S):- Num =:= S * S.
is_square_help(Num, S):- 
    Num > S * S,
    T is S+1,
    is_square_help(Num, T).
is_square_help(Num, S):- Num < S * S, fail.

contains(_, []):- fail.
contains(Needle, [Needle|_]).
contains(Needle, [_|Tail]):- contains(Needle, Tail).

nums(0, []).
nums(Num, List) :- length(List, Num), nums_help(Num, List).

nums_help(0, _).
nums_help(Num, List) :- 
    contains(Num, List),
    X is Num - 1,
    nums_help(X, List).

square_sum(Num, List) :- 
    nums(Num, List),
    square_sum_help(List).

square_sum_help([X, Y|T]) :- 
    Z is X + Y,
    is_square(Z),
    square_sum_help(T).

目前,当我运行时square_sum(15, List).,程序不会终止.我已经离开它大约10分钟,它只是继续运行.我知道有些问题需要很长时间才能解决,但据报道其他问题产生了毫秒级的答案.我在这做错了什么？

Answer 1

SWI-Prolog 允许这种紧凑的实现

square_sum(N,L) :-
    numlist(1,N,T),
    select(D,T,R),
    adj_squares(R,[D],L).

adj_squares([],L,R) :- reverse(L,R).
adj_squares(T,[S|Ss],L) :-
    select(D,T,R),
    float_fractional_part(sqrt(S+D))=:=0,
    adj_squares(R,[D,S|Ss],L).

N=15 时完成速度非常快

按照建议进行编辑，按顺序构建列表会产生更好的代码：

square_sum(N,L) :-
    numlist(1,N,T),
    select(D,T,R),
    adj_squares(R,D,L).

adj_squares([],L,[L]).
adj_squares(T,S,[S|L]) :-
    select(D,T,R),
    float_fractional_part(sqrt(S+D))=:=0,
    adj_squares(R,D,L).

编辑

当 N 增长时，上面的代码变得太慢。我改变了策略，现在尝试找到进入由二元关系引起的图形的哈密顿路径。对于 N=15，它看起来像

（以下是生成 Graphviz 脚本的代码：

square_pairs(N,I,J) :-
    between(1,N,I),
    I1 is I+1,
    between(I1,N,J),
    float_fractional_part(sqrt(I+J))=:=0.
square_pairs_graph(N) :-
    format('graph square_pairs_N_~d {~n', [N]),
    forall(square_pairs(N,I,J), format(' ~d -- ~d;~n', [I,J])),
    writeln('}').

）

这里是查找路径的代码

hamiltonian_path(N,P) :-
    square_pairs_struct(N,G),
    between(1,N,S),
    extend_front(1,N,G,[S],P).

extend_front(N,N,_,P,P) :- !.
extend_front(Len,Tot,G,[Node|Ins],P) :-
    arg(Node,G,Arcs),
    member(T,Arcs),
    \+memberchk(T,Ins),
    Len1 is Len+1,
    extend_front(Len1,Tot,G,[T,Node|Ins],P).


struct_N_of_E(N,E,S) :-
    findall(E,between(1,N,_),As),
    S=..[graph|As].

square_pairs_struct(N,G) :-
    struct_N_of_E(N,[],G),
    forall(square_pairs(N,I,J), (edge(G,I,J),edge(G,J,I))).
edge(G,I,J) :-
    arg(I,G,A), B=[J|A], nb_setarg(I,G,B).