的Prolog：如何優化這個代碼（求解123456789 = 100拼圖）

Question

因此就出現了一個難題：

這個方程是不完整的：1 2 3 4 5 6 7 8 9 = 100.一個方法，使 它準確的是通過添加七個加號和減號，如下所示：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 

即使我搜索了所有可能的解決方案，您的功能已經運行得非常快。它只挑6個X的; 42個Y's; 224個Z's;和15個Q's。我不認爲優化會值得您享受。但是如果你真的想：我選擇一個X後立即放置一個測試函數來測試它。它將6個X減少到3個（全部找到解決方案之前）。 42歲至30歲; 224 Z到184;而15個Q的值爲11.我相信在挑選Y之後立即進行測試可以進一步降低它，以查看X YSign Y是否已經很大或者很小，以至於無法解決問題。

在計算密集程度更高的PROLOG計劃中，早些時候在'generate and test' algorithms中放置「測試」的部分可以提供很多幫助。