SEND + MORE = MONEY 的 Prolog 实现没有找到结果

问题描述 投票：0回答：4

我开始使用 Prolog，并决定尝试著名的 SEND+MORE=MONEY 难题，因为它看起来相当简单。但是，我的实现确实找到了结果。

谁能看出我做错了什么？

smm([S, E, N, D, M, O, R, Y]) :-
  maplist(between(0, 9), [S, E, N, D, M, O, R, Y]),
  Line1 is           S*1000 + E*100 + N*10 + D,
  Line2 is           M*1000 + O*100 + R*10 + E,
  Sum   is M*10000 + O*1000 + N*100 + E*10 + Y,
  Sum = Line1 + Line2.

我不确定这是否是解决这个难题的最佳方法，所以请随时对我的代码提出任何（建设性的！）意见。

更新： 以防万一有人来这里寻找难题的解决方案，上面的代码无论如何都行不通，因为我忘记了两个重要的约束条件，即

M
不应该为零，并且没有两个变量应该是相同的数字。

我修改后的有效代码如下，但请注意它很慢。与 brebs 在下面发布的代码相比，在我的机器上解决了大约 84 秒，解决它的速度比我看到的要快！

smm([S, E, N, D, M, O, R, Y]) :-
  maplist(between(0, 9), [S, E, N, D, M, O, R, Y]),
  M =\= 0,
  unique([S, E, N, D, M, O, R, Y]),
  Line1 is           S*1000 + E*100 + N*10 + D,
  Line2 is           M*1000 + O*100 + R*10 + E,
  Sum   is M*10000 + O*1000 + N*100 + E*10 + Y,
  Sum   is Line1 + Line2.

unique([]).
unique([H|T]) :- not(memberchk(H, T)), unique(T).
prolog cryptarithmetic-puzzle
4个回答
2
投票

首先，这个问题更适合 。请参阅这些问题。

你怎么会自己发现那个错误？毕竟，并不是每一个错误都那么容易被发现。这是一种方法，您可以在遇到 意外失败.

的任何情况下应用 
:- op(950, fy, *)。

*_G_0。

smm(_/*[S, E, N, D, M, O, R, Y]*/) :-
   地图列表（介于（0、9）、[S、E、N、D、M、O、R、Y]），
   * Line1 是 S*1000 + E*100 + N*10 + D,
   * Line2 是 M*1000 + O*100 + R*10 + E,
   总和为 M*10000 + O*1000 + N*100 + E*10 + Y，
   总和 = Line1 + Line2。

?- smm(Xs)。
   假的，出乎意料的。 % 需要相当长的时间

因为这个片段已经失败了，所以你原来的程序也失败了。我们可以通过扩展 

maplist/2
.

进一步阐述这一点 
smm(_/*[S, E, N, D, M, O, R, Y]*/) :-
   * 在(0, 9, S)之间，
   在（0、9、E）之间，
   在（0、9、N）之间，
   * 在(0, 9, D)之间，
   在（0、9、M）之间，
   在（0、9、O）之间，
   * 在(0, 9, R)之间，
   在（0、9、Y）之间，
   * Line1 是 S*1000 + E*100 + N*10 + D,
   * Line2 是 M*1000 + O*100 + R*10 + E,
   总和为 M*10000 + O*1000 + N*100 + E*10 + Y，
   总和 = Line1 + Line2。

?- smm(Xs)。
   假的，出乎意料的。 ％ 快多了

所以在剩下的可见部分的任何地方都一定有错误。

1
投票

正如您使用

is
来计算
Line1
、
Line2
和
Sum
的算术表达式一样，您需要将它用于
Line1 + Line2
。

1
投票

几个月前，我调整了一个我在网上找到的解决方案（不再存在）。不是说它是完美的代码，而是值得深思的地方：

all_diff(L) :-
    \+ (append(_,[X|R],L), memberchk(X,R)).

digit(N) :-
    between(0, 9, N).

carry(0).
carry(1).

go:-
    send_more_money([S,E,N,D,M,O,R,Y]),
    result([S,E,N,D,M,O,R,Y]).

result([S,E,N,D,M,O,R,Y]):-
    nl, write('  S E N D'), tab(5), out([' ', S, E, N, D]),
    nl, write('  M O R E'), tab(5), out([' ', M, O, R, E]),
    nl, write('---------'), tab(5), write(--------------),
    nl, write('M O N E Y'), tab(5), out([M, O, N, E, Y]),
    nl.

out([]).
out([C | Rest]) :-
    write(C),
    write(' '),
    out(Rest).

send_more_money(Ds):-
    Ds = [S, E, N, D, M, O, R, Y],
    % A multi-digit number cannot start with 0
    dif(M, 0),
    column(0, 0, C2, M,  0),  % Cn are the carries
    column(S, M, C3, O, C2),
    column(E, O, C4, N, C3),
    column(N, R, C4, E, C5),
    column(D, E,  0, Y, C5),
    all_diff(Ds).

column(DigitInLine1, DigitInLine2, Carry, DigitInLine3, NewCarry) :-
    carry(Carry),  % try 0 and 1 in turn
    digit(DigitInLine1),
    digit(DigitInLine2),
    Sum is DigitInLine1 + DigitInLine2 + Carry,
    NewCarry is Sum // 10,
    DigitInLine3 is Sum - (10 * NewCarry).

:- writeln('The puzzle SEND+MORE=MONEY has been loaded').
:- writeln('To solve it: go.').

swi-prolog 中的结果：

?- time(go).

  S E N D       9 5 6 7 
  M O R E       1 0 8 5 
---------     --------------
M O N E Y     1 0 6 5 2 
% 2,436 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 5432383 Lips)
true ;
% 1,223 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 10963792 Lips)
false.

这是一个（整理但较慢的）变化：

send_more_money(Ds):-
    Ds = [S, E, N, D, M, O, R, Y],
    numlist(0, 9, NL),
    % A multi-digit number cannot start with 0
    dif(M, 0),
    digits_perm(Ds, NL),
    column(D, E,  0, Y, C1),
    column(N, R, C1, E, C2),
    column(E, O, C2, N, C3),
    column(S, M, C3, O, C4),
    column(0, 0, C4, M,  0).  % Cn are the carries

column(DigitInLine1, DigitInLine2, Carry, DigitInLine3, NewCarry) :-
    Sum is DigitInLine1 + DigitInLine2 + Carry,
    NewCarry is Sum // 10,
    DigitInLine3 is Sum - (10 * NewCarry).

digits_perm([], _).
digits_perm([H|T], NL) :-
    select(H, NL, NL0),
    digits_perm(T, NL0).

swi-prolog 中的结果：

?- time(send_more_money(Ds)).
% 12,984,725 inferences, 0.782 CPU in 0.782 seconds (100% CPU, 16600060 Lips)
Ds = [9, 5, 6, 7, 1, 0, 8, 2] ;
% 480,046 inferences, 0.030 CPU in 0.030 seconds (100% CPU, 16230337 Lips)
false.
0
投票

这是一个通用的求解器：

add_digits_09(DigRows, DigSum) :-
    reverse_lists(DigRows, DigRowsR),
    reverse(DigSum, DigSumR),
    numlist(0, 9, Digits),
    % Start digit cannot be zero
    DigSum = [DSH|_],
    dif(DSH, 0),
    add_digits_09_(DigSumR, DigRowsR, Digits, 0).

add_digits_09_([], _, _, 0).
add_digits_09_([Sum|DigSum], DigRows, Digits, Carry) :-
    % Sum the column
    sum_column(DigRows, Digits, Carry, ColSum, Digits0, DigRows0),
    (   ColSum < 10
    ->  Sum = ColSum,
        Carry1 = 0
    ;   Sum is ColSum - 10,
        Carry1 = 1
    ),
    digit_select(Sum, Digits0, Digits00),
    add_digits_09_(DigSum, DigRows0, Digits00, Carry1).

reverse_lists([], []).
reverse_lists([H|T], [R|Rs]) :-
    reverse(H, R),
    reverse_lists(T, Rs).

sum_column(DigRows, Digits, Carry, ColSum, Digits0, DigRows0) :-
    sum_column_(DigRows, Digits, 0, ColSum0, Digits0, DigRows0),
    ColSum is ColSum0 + Carry.

sum_column_([], Digits, Sum, Sum, Digits, []).
% F means final
sum_column_([H|T], Digits, Upto, Sum, Digits0F, [DT|DigRows0]) :-
    H = [D|DT],
    digit_select(D, Digits, Digits0),
    Upto1 is Upto + D,
    sum_column_(T, Digits0, Upto1, Sum, Digits0F, DigRows0).

digit_select(D, Digits, Digits0) :-
    (   var(D)
    ->  select(D, Digits, Digits0)
    % Ensure is gone from list
    ;   select(D, Digits, Digits0)
    ->  true
    % Is already gone
    ;   Digits0 = Digits
    ).

swi-prolog 中的结果：

?- time(add_digits_09([[0,S,E,N,D], [0,M,O,R,E]], [M,O,N,E,Y])).
% 156,397 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 24700704 Lips)
S = 9,
E = 5,
N = 6,
D = 7,
M = 1,
O = 0,
R = 8,
Y = 2 ;
% 43,689 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 22319777 Lips)
false.

?- time(add_digits_09([[0,0,E,A,T], [0,T,H,A,T]], [A,P,P,L,E])).
% 21,141 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 17262144 Lips)
E = 8,
A = 1,
T = 9,
H = 2,
P = 0,
L = 3 ;
% 2,153 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 5315918 Lips)
false.

?- A = 7, time(add_digits_09([[0,C,R,O,S,S], [0,R,O,A,D,S]], [D,A,N,G,E,R])).
% 26,171 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 9876777 Lips)
A = G, G = 7,
C = 9,
R = N, N = 8,
O = 0,
S = 4,
D = 1,
E = 5 ;
% 34,899 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 5704604 Lips)
false.
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.