序言Cryptarithmetic益智

我已要求使用Prolog的解決Cryptarithmetic困惑：序言Cryptarithmetic益智

GIVE 
* ME 
------ 
MONEY

以上是難題，我想不出哪裏出了問題，結果總是返回false。另外，我不允許在SWI-Prolog中使用任何庫。

solve(Z) :- 
    assign(Z,[0,1,2,3,4,5,6,7,8,9]), 
    check(Z). 

find(VAL , G,I,V,E ) :- VAL is G * 1000 + I * 100 + V * 10 + E. 
find2(VALR, M,E  ) :- VALR is M * 10 + E. 
find3(VALA, M,O,N,E,Y) :- VALA is M * 10000 + O * 1000 + N * 100 + E * 10 + Y. 

check(Z) :- 
    G #>= 1, 
    M #>= 1, 
    find(VAL, G,I,V,E), 
    find2(VALR, M,E), 
    find3(VALA, M,O,N,E,Y), 
    VAL * VALR =:= VALA. 

assign(Z,L) :- 
    permute(L,Z). 

/* permute is similar to all_different in swi-prolog */ 
addany(X,K,[X|K]). 
addany(X,[F|K],[F|L1]) :- 
    addany(X,K,L1). 

permute([],[]). 
permute([X|K],P) :- 
    permute(K,L1), 
    addany(X,L1,P).

樣品查詢：

?- solve([G,I,V,E,M,O,N,Y]). 
false.       % fails unexpectedly

來源

2011-04-15 kyo

下面由Eric Weisstein和埃德·佩格article將是有益的。它爲Mathematica中的類似問題提供了幾種解決方案。

使用非常蠻力的方法，有兩種解決方案：1072 * 92 = 98624和1092 * 72 = 78624。我使用的代碼爲：

In[16]:= Cases[ 
Permutations[ 
    Range[0, 9], {5}], {g_, i_, v_, e_, m_} /; g > 0 && m > 0 :> 
    With[{dig = IntegerDigits[(g*10^3 + i*10^2 + v*10 + e) (10 m + e)]}, 
    Join[{g, i, v, e, m}, dig[[{2, 3, 5}]]] /; 
    And[Length[dig] == 5, Unequal @@ dig, dig[[{1, 4}]] == {m, e}, 
    Intersection[dig[[{2, 3, 5}]], {g, i, v, e, m}] === {} ] 
    ]] 

Out[16]= {{1, 0, 7, 2, 9, 8, 6, 4}, {1, 0, 9, 2, 7, 8, 6, 4}}

來源

2011-04-17 20:52:38 Sasha

好吧，Mathematica與Prolog不是很相似。（事實上，除了Prolog之外，沒有任何一種語言與Prolog非常相似，就此而言......）[事實上，OP代碼中的錯誤可能是「置換」，所以像Mathematica的內置置換這樣的東西超出了OP的範圍。 ] – ShreevatsaR 2011-04-17 20:55:08

@ShreevatsaR。 'permute'的實現並不是真正的問題。有關詳細信息，請參閱我的上述答案 – repeat 2015-08-13 00:50:55

讓我們來看看問題的核心！

每置換 [0,1,2,3,4,5,6,7,8,9]是長度10的列表。
[G,I,V,E,M,O,N,Y]是一個列表長度8。
[0,1,2,3,4,5,6,7,8,9]的排列可以統一爲[G,I,V,E,M,O,N,Y]。

作爲速戰速決，適應的check/1這樣的定義：

 
check([G,I,V,E,M,O,N,Y,_,_]) :- 
    find(VAL, G,I,V,E), 
    G >= 1, 
    find2(VALR, M,E), 
    M >= 1, 
    find3(VALA, M,O,N,E,Y), 
    VAL * VALR =:= VALA.

然後，運行下面的「固定」查詢：

 
?- Expr = ([G,I,V,E]*[M,E] = [M,O,N,E,Y]), 
    Zs = [G,I,V,E,M,O,N,Y,_,_], 
    time(solve(Zs)). 
% 24,641,436 inferences, 7.692 CPU in 7.709 seconds (100% CPU, 3203506 Lips) 
Expr = ([1,0,7,2] * [9,2] = [9,8,6,2,4]), 
Zs = [1,0,7,2,9,8,6,4,3,5] ; 
% 7,355 inferences, 0.007 CPU in 0.007 seconds (100% CPU, 1058235 Lips) 
Expr = ([1,0,7,2] * [9,2] = [9,8,6,2,4]),  % redundant 
Zs = [1,0,7,2,9,8,6,4,5,3] ; 
% 6,169,314 inferences, 1.935 CPU in 1.939 seconds (100% CPU, 3188312 Lips) 
Expr = ([1,0,9,2] * [7,2] = [7,8,6,2,4]), 
Zs = [1,0,9,2,7,8,6,4,3,5] ; 
% 7,355 inferences, 0.005 CPU in 0.005 seconds (99% CPU, 1360603 Lips) 
Expr = ([1,0,9,2] * [7,2] = [7,8,6,2,4]),  % redundant 
Zs = [1,0,9,2,7,8,6,4,5,3] ; 
% 6,234,555 inferences, 1.955 CPU in 1.959 seconds (100% CPU, 3189462 Lips) 
false.

這裏的另一種方式解決問題：

首先，使用clpfd！

:- use_module(library(clpfd)).

二，（再）使用my answer 早些時候向相關的問題Faster implementation of verbal arithmetic in Prolog代碼：

 
?- Expr = ([G,I,V,E] * [M,E] #= [M,O,N,E,Y]), 
    Zs = [G,I,V,E,M,O,N,Y], 
    crypt_arith_(Expr,Zs), 
    time(labeling([],Zs)). 
% 397,472 inferences, 0.088 CPU in 0.088 seconds (100% CPU, 4521899 Lips) 
Expr = ([1,0,7,2] * [9,2] #= [9,8,6,2,4]), Zs = [1,0,7,2,9,8,6,4] ; 
% 128,982 inferences, 0.037 CPU in 0.037 seconds (100% CPU, 3502788 Lips) 
Expr = ([1,0,9,2] * [7,2] #= [7,8,6,2,4]), Zs = [1,0,9,2,7,8,6,4] ; 
% 77,809 inferences, 0.028 CPU in 0.028 seconds (100% CPU, 2771783 Lips) 
false.

沒有多餘的解決方案。數量級比「生成&測試」快。 clpfd岩石！

來源

2015-08-12 18:27:08 repeat

序言Cryptarithmetic益智

回答

相關問題