让我们来看看问题的核心!
- 每置换
[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岩石!
好吧,Mathematica与Prolog不是很相似。 (事实上,除了Prolog之外,没有任何一种语言与Prolog非常相似,就此而言......)[事实上,OP代码中的错误可能是“置换”,所以像Mathematica的内置置换这样的东西超出了OP的范围。 ] – ShreevatsaR 2011-04-17 20:55:08
@ShreevatsaR。 'permute'的实现并不是真正的问题。有关详细信息,请参阅我的上述答案 – repeat 2015-08-13 00:50:55