プロローグ：このコードを最適化する方法（123456789 = 100パズルを解く）

Question

だからパズルがあったが：

この式が不完全である：せる1 2 3 4 5 6 7 8 9 = 100片道 正確には、次のように7つのプラス記号とマイナス記号を追加します。1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100 3つのプラス記号またはマイナス記号を使ってどうやってやりますか？

私はプロローグに非常に新しいですが、パズルを解く、しかし、私は

makeInt(S,F,FinInt):- 
    getInt(S,F,0,FinInt). 

getInt(Start, Finish, Acc, FinInt):- 
    0 =< Finish - Start, 
    NewAcc is Acc*10 + Start, 
    NewStart is Start +1, 
    getInt(NewStart, Finish, NewAcc, FinInt). 
getInt(Start, Finish, A, A):- 
    0 > Finish - Start. 

itCounts(X,Y,Z,Q):- 
    member(XLastDigit,[1,2,3,4,5,6]), 
    FromY is XLastDigit+1, 
    numlist(FromY, 7, ListYLastDigit), 
    member(YLastDigit, ListYLastDigit), 
    FromZ is YLastDigit+1, 
    numlist(FromZ, 8, ListZLastDigit), 
    member(ZLastDigit,ListZLastDigit), 
    FromQ is ZLastDigit+1, 
    member(YSign,[-1,1]), 
    member(ZSign,[-1,1]), 
    member(QSign,[-1,1]), 
    0 is XLastDigit + YSign*YLastDigit + ZSign*ZLastDigit + QSign*9, 
    makeInt(1, XLastDigit, FirstNumber), 
    makeInt(FromY, YLastDigit, SecondNumber), 
    makeInt(FromZ, ZLastDigit, ThirdNumber), 
    makeInt(FromQ, 9, FourthNumber), 
    X is FirstNumber, 
    Y is YSign*SecondNumber, 
    Z is ZSign*ThirdNumber, 
    Q is QSign*FourthNumber, 
    100 =:= X + Y + Z + Q. 

Answer 1

ないこれは、最適化の略確かにそれを最適化する方法を疑問に思います。コードは単に短いです：

sum_123456789_eq_100_with_3_sum_or_sub(L) :- 
    append([G1,G2,G3,G4], [0'1,0'2,0'3,0'4,0'5,0'6,0'7,0'8,0'9]), 
    maplist([X]>>(length(X,N), N>0), [G1,G2,G3,G4]), 
    maplist([G,F]>>(member(Op, [0'+,0'-]),F=[Op|G]), [G2,G3,G4], [F2,F3,F4]), 
    append([G1,F2,F3,F4], L), 
    read_term_from_codes(L, T, []), 
    100 is T. 

Answer 2

それは私にしばらく時間がかかったが、私はあなたのコードが何をしているかです。これは次のようなものです：

itCounts(X,Y,Z,Q) :- % generate X, Y, Z, and Q s.t. X+Y+Z+Q=100, etc. 
    generate X as a list of digits 
    do the same for Y, Z, and Q 
    pick the signs for Y, Z, and Q 
    convert all those lists of digits into numbers 
    verify that, with the signs, they add to 100. 

ここで非効率とは、テストがすべて最後に行われたことです。数字のいずれかを選ぶとすぐに、できるだけ早くテストを行うことができれば、効率を向上させることができます。

itCounts(X,Y,Z,Q) :- % generate X, Y, Z, and Q s.t. X+Y+Z+Q=100, etc. 
    generate X as a list of digits, and convert it to a number 
    if it's so big or small the rest can't possibly bring the sum back to 100, fail 
    generate Y as a list of digits, convert to number, and pick it sign 
    if it's so big or so small the rest can't possibly bring the sum to 100, fail 
    do the same for Z 
    do the same for Q 

可能性のあるすべてのソリューションを検索しても、機能はかなり早く実行されています。それは6Xだけを選ぶ。 42歳224 Z's; 15 Qのです。私は最適化があなたの価値があるとは思わない。

あなたが本当にしたいのは、Xを選択した直後にテスト機能を入れてテストしました.6個のXを3に減らしました。 42歳から30歳。 224 Z〜184; XのYSign Yが既に大きすぎるか小さかったかどうかを調べるために、Yが選択された直後にテストすることで、それをさらに減らすことができると考えています。

より計算量の多いPROLOGプログラムでは、先に 'test'の部分を'generate and test' algorithmsに置くことで多くの助けになります。