Prolog 密码谜题

Question

我被要求使用 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

Answer 1

让我们直击问题的核心!

每一个排列[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.

Then, run the following "fixed" query:

?- 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]),      % redundantZs   = [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]),      % redundantZs   = [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.

---

Here's another way to solve the problem:

First, use 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),
时间(标签([]，Zs))。
% 397,472 推理，0.088 秒内 0.088 CPU(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 唇)
错误的。

没有多余的解决方案。比“生成和测试”快几个数量级。 clpfd岩石!