cryptarithmetic puzzle (prolog)

Tag: prolog Author: a4332659 Date: 2012-07-24

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?

a very closely related question:

Best Answer

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.

comments:

There's no solution to rob+bert=nores: bach.istc.kobe-u.ac.jp/llp/crypt.html
@Haile: Thanks for the link. I improved the answer with that info...
@gusbro thanks!