4

I was asked to write a Prolog code to solve the cryptarithmetic puzzle, using "generate and test". For example I get solve([R,O,B],[B,E,R,T],[N,O,R,E,S]) and I need to find an assign for the letters. So I wrote this code: 

sum(List1,List2,SumList) :-
    append(List1,List2,List3),
    append(List3,SumList,AllList),
    assign([0,1,2,3,4,5,6,7,8,9],AllList),
    add_zero(List1,List1Z),
    add_zero(List2,List2Z),
    add_zero(SumList,SumListZ),
    name(Num1,List1Z),
    name(Num2,List2Z),
    name(SumNum,SumListZ),
    SumNum is Num1+Num2,
    !.

remove(X,[X|Xs],Xs).
remove(X,[_|Ys],Res) :-
    remove(X,Ys,Res).

assign(Digits,[X|Tail]) :-
    nonvar(X),
    !,
    assign(Digits,Tail).
assign(Digits,[X|Tail]) :-
    remove(X,Digits,D1),
    assign(D1,Tail).
assign(_,[]) :-
    !.

add_zero([X|Tail1],[Y|Tail2]) :-
    !,
    Y is X+48,
    add_zero(Tail1,Tail2).
add_zero([],[]) :-
    !.

But I have a bug and I can't find it... can you help me?

repeat
  • 18,496
  • 4
  • 54
  • 166
Ygandelsman
  • 453
  • 7
  • 16
  • 2
    a very closely related question: http://stackoverflow.com/questions/10925285/faster-implementation-of-verbal-arithmetic-in-prolog – Will Ness Aug 09 '12 at 20:35
  • Hello this is an old question thread but I have a problem understanding it. add_zero([X|Tail1],[Y|Tail2]) :- !, Y is X+48, add_zero(Tail1,Tail2). Why Y is X+48 ? What does 'add_zero' function do here? Could you please help me understand. Thank you. – Clojurevangelist Mar 24 '19 at 09:33

1 Answers1

3

The problem with your code is that in the second clause of remove/3 you are not keeping the item which is not removed. It should read:

remove(X,[Y|Ys],[Y|Res]):-
    remove(X,Ys,Res).

I tried your code with SEND + MORE = MONEY and it worked fine after fixing that procedure.

However it did not find a solution for ROB + BERT = NORES... According to this site, which has many solvers, your equation has no solution.

gusbro
  • 22,357
  • 35
  • 46