4

我被要求使用 Prolog 解决一个密码算术难题：

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
4

2 回答 2

2

让我们进入问题的核心！

  • 的每个排列 都是一个长度为 10[0,1,2,3,4,5,6,7,8,9]的列表。
  • [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：

检查（[G，I，V，E，M，O，N，Y，_，_]）：-
   查找（VAL，G，I，V，E），
   G >= 1 ,
   查找2（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,_,_] ,
   时间（解决（Zs））。
% 24,641,436 次推理，7.692 CPU 在7.709秒内（100% CPU，3203506 唇）
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 次推理，0.007秒内 0.007 CPU（100% CPU，1058235 唇）
expr = ([1,0,7,2] * [9,2] = [9,8,6,2,4]), %冗余
Zs = [1,0,7,2,9,8,6 ,4, 5,3 ] ;
% 6,169,314 推理，1.935 CPU 在1.939秒内（100% CPU，3188312 唇）
表达式 = ([1,0,9,2] * [7,2] = [7,8,6,2,4]),
Zs = [1,0,9,2,7,8,6,4, 3,5 ]；
% 7,355 次推理，0.005秒内 0.005 CPU（99% CPU，1360603 唇）
expr = ([1,0,9,2] * [7,2] = [7,8,6,2,4]), %冗余
Zs = [1,0,9,2,7,8,6 ,4, 5,3 ] ;
% 6,234,555 推理，1.955 CPU 在1.959秒内（100% CPU，3189462 唇）
错误的。

这是解决问题的另一种方法：

首先，使用！

:- use_module(library(clpfd)).

其次，（重新）使用我之前 对相关问题的回答中提供的代码更快地在 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),
   时间（标签（[]，Zs））。
% 397,472 推理，0.088 CPU 在0.088秒内（100% CPU，4521899 唇）
Expr = ([1,0,7,2] * [9,2] #= [9,8,6,2,4]), Zs = [1,0,7,2,9,8,6, 4];
% 128,982 次推理，0.037秒内 0.037 CPU（100% CPU，3502788 唇）
Expr = ([1,0,9,2] * [7,2] #= [7,8,6,2,4]), Zs = [1,0,9,2,7,8,6, 4];
% 77,809 次推理，0.028秒内 0.028 CPU（100% CPU，2771783 唇）
错误的。

没有多余的解决方案。比“生成和测试”快几个数量级。摇滚！

于 2015-08-12T18:27:08.847 回答
0

Eric Weisstein 和 Ed Pegg的以下文章将很有用。它为 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-17T20:52:38.683 回答