2

この述語を機能させるのに問題があります。アイデアはdiabolic([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P])、そのリスト内のすべての可能な魔方陣を取得するために使用することです。

最初は使用することを考えpermutation/2ましたが、16個の数字のリストでは非常に遅いです。

次に、外部ライブラリ（clpfd）を使用して素晴らしいパフォーマンスを発揮する例を見つけましたが、外部ライブラリなしで解決しようとしています...だから、次のようなことを試しました：

sum([X,Y,Z,W]) :-
  A = [1..16],
  member(X,A),
  member(Y,A),
  member(Z,A),
  member(W,A),
  X \== Y,
  X \== Z,
  X \== W,
  Y \== Z,
  Y \== W,
  Z \== W,
  34 is (X+Y+Z+W).

そこで私がやろうとしているのは、合計が 34 になるさまざまな数のすべての可能なリストを取得することです。これにより、どの組み合わせが魔方陣になるかを確認できます (通常の順列を使用するよりも速くすることを期待しています.

それでも、一部の Operator Expected に関するエラーが発生するmember(X,[1..16]),ので、何か間違っている可能性があります。私は Prolog にかなり慣れていないので、皆さんから助けを得たいと思っていました。

前もって感謝します。

4

2 に答える 2

0

あなたは正しい道を進んでいます。検索スペースを削減するために、できるだけ早く制約を適用してください。

問題は、順列プロセスを「分割」して、結果をできるだけ早く切り捨てることができるようにする方法です。

シンプルな方法：

diabolic([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P]) :-
    N0=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],

    R1=[A,B,C,D],select_list(N0,R1,N1),sum_list(R1,34),
    R2=[E,F,G,H],select_list(N1,R2,N2),sum_list(R2,34),
    R3=[I,J,K,L],select_list(N2,R3,N3),sum_list(R3,34),
    R4=[M,N,O,P],select_list(N3,R4,[]),sum_list(R4,34),

    sum_list([A,E,I,M],34),
    sum_list([B,F,J,N],34),
    sum_list([C,G,K,O],34),
    sum_list([D,H,L,P],34),

    sum_list([A,F,K,P],34),
    sum_list([M,J,G,D],34).

select_list(X,[],X).
select_list(X,[H|T],Z) :- select(H,X,Y), select_list(Y,T,Z).

これはまだ CLP(FD) よりもはるかに遅いですが、出発点になる可能性があります...

簡単なコードの改善を編集します。

元のパフォーマンス:

?- forall(time(diabolic(L)),writeln(L)).
% 74,769,227 inferences, 23.739 CPU in 23.754 seconds (100% CPU, 3149688 Lips)
[1,2,15,16,12,14,3,5,13,7,10,4,8,11,6,9]
% 7,556,909 inferences, 2.396 CPU in 2.448 seconds (98% CPU, 3154252 Lips)
[1,2,15,16,13,14,3,4,12,7,10,5,8,11,6,9]
% 90,103,270 inferences, 28.475 CPU in 28.503 seconds (100% CPU, 3164265 Lips)
[1,2,16,15,13,14,4,3,12,7,9,6,8,11,5,10]
Action (h for help) ? aabort

select_list/3 のインライン化

select_(N0,[A,B,C,D],N1) :-
    select(A,N0,T0),
    select(B,T0,T1),
    select(C,T1,T2),
    select(D,T2,N1).

diabol_1([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P]) :-
    N0=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],
    R1=[A,B,C,D],select_(N0,R1,N1),sum_list(R1,34),
    R2=[E,F,G,H],select_(N1,R2,N2),sum_list(R2,34),
    R3=[I,J,K,L],select_(N2,R3,N3),sum_list(R3,34),
    R4=[M,N,O,P],select_(N3,R4,[]),sum_list(R4,34),

    sum_list([A,E,I,M],34),
    sum_list([B,F,J,N],34),
    sum_list([C,G,K,O],34),
    sum_list([D,H,L,P],34),

    sum_list([A,F,K,P],34),
    sum_list([M,J,G,D],34).

小さな改善が得られます。

?- forall(time(diabol_1(L)),writeln(L)).
% 65,282,719 inferences, 21.137 CPU in 21.195 seconds (100% CPU, 3088524 Lips)
[1,2,15,16,12,14,3,5,13,7,10,4,8,11,6,9]
% 6,607,508 inferences, 2.074 CPU in 2.075 seconds (100% CPU, 3186362 Lips)
[1,2,15,16,13,14,3,4,12,7,10,5,8,11,6,9]
% 78,691,563 inferences, 24.914 CPU in 24.928 seconds (100% CPU, 3158505 Lips)
[1,2,16,15,13,14,4,3,12,7,9,6,8,11,5,10]
Action (h for help) ? aabort

sum_list/2 をインライン化すると、さらに小さなゲインが得られます。

sum_([A,B,C,D]) :- A+B+C+D =:= 34.

diabol_2([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P]) :-
    N0=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],
    R1=[A,B,C,D],select_(N0,R1,N1),sum_(R1),
    R2=[E,F,G,H],select_(N1,R2,N2),sum_(R2),
    R3=[I,J,K,L],select_(N2,R3,N3),sum_(R3),
    R4=[M,N,O,P],select_(N3,R4,[]),sum_(R4),

    sum_([A,E,I,M]),
    sum_([B,F,J,N]),
    sum_([C,G,K,O]),
    sum_([D,H,L,P]),

    sum_([A,F,K,P]),
    sum_([M,J,G,D]).

?- forall(time(diabol_2(L)),writeln(L)).
% 20,419,167 inferences, 10.425 CPU in 10.431 seconds (100% CPU, 1958699 Lips)
[1,2,15,16,12,14,3,5,13,7,10,4,8,11,6,9]
% 2,058,108 inferences, 1.046 CPU in 1.047 seconds (100% CPU, 1966993 Lips)
[1,2,15,16,13,14,3,4,12,7,10,5,8,11,6,9]
% 24,592,123 inferences, 12.462 CPU in 12.481 seconds (100% CPU, 1973394 Lips)
[1,2,16,15,13,14,4,3,12,7,9,6,8,11,5,10]
Action (h for help) ? aabort
于 2014-05-31T19:39:54.260 に答える