Search code examples
mathprologcryptarithmetic-puzzle

Cryptarithmetic Multiplication Prolog


I have the grasp of the idea of crypt arithmetic and addition but I cannot figure out how to do a multiplication crypt arithmetic problem. It's simply TWO*SIX=TWELVE or something along those lines without the middle additional part of the multiplication problem given. I couldn't find anything online and I already found some constraints for the problem but nothing to leads me to some answers. Not sure where to ask this and thought this would be the best place.

I want to know how to solve a multiplication crypt arithmetic problem.

I already concluded:

         T  W  O
*        S  I  X
_________________
T  W  E  L  V  E


T \= 0 which also means S \= 0
T is 1-6
E is (O*X) mod 10
O or X cannot be 0 or 1 since E has to be different and 0 or 1 gives the same value 
as either O or X.

EDIT: I was using the generate and test method

solve(T,W,O,S,I,X,E,L,V) :-
        X = [T,W,O,S,I,X,E,L,V],
        Digits = [0,1,2,3,4,5,6,7,8,9],
        assign_digits(X, Digits),
        T > 0, 
        S > 0,
        100*T + 10*W + O * 100*S + 10*I + X =:=
        100000*T + 10000*W + 1000*E + 100*L + 10*V + E,
        write(X).

select(X, [X|R], R).
select(X, [Y|Xs], [Y|Ys]):- select(X, Xs, Ys).

assign_digits([], _List).
assign_digits([D|Ds], List):-
        select(D, List, NewList),
        assign_digits(Ds, NewList).

Solution

  • Trivially to do with constraint logic programming. For example, in ECLiPSe Prolog:

    :- lib(ic).
    puzzle(Vars) :-
        [T,W,O,S,I,X,E,L,V] = Vars,
        Vars :: 0..9,
        alldifferent(Vars),
        T #> 0, S #> 0,
        (100*T + 10*W + O) * (100*S + 10*I + X) #= 
          100000*T + 10000*W + 1000*E + 100*L + 10*V + E,
        labeling(Vars).
    

    First solution:

    [eclipse]: puzzle([T,W,O,S,I,X,E,L,V]).
    T = 1
    W = 6
    O = 5
    S = 9
    I = 7
    X = 2
    E = 0
    L = 3
    V = 8
    Yes (0.01s cpu, solution 1, maybe more) ? 
    

    There are 3 different solutions:

    [eclipse]: puzzle([T,W,O,S,I,X,E,L,V]), writeln([T,W,O,S,I,X,E,L,V]), fail.
    [1, 6, 5, 9, 7, 2, 0, 3, 8]
    [2, 1, 8, 9, 6, 5, 0, 3, 7]
    [3, 4, 5, 9, 8, 6, 0, 1, 7]
    No (0.02s cpu)
    

    Update - translation to SWI Prolog:

    :- use_module(library(clpfd)).
    puzzle(Vars) :-
        [T,W,O,S,I,X,E,L,V] = Vars,
        Vars ins 0..9,
        all_different(Vars),
        T #> 0, S #> 0,
        (100*T + 10*W + O) * (100*S + 10*I + X) #= 
          100000*T + 10000*W + 1000*E + 100*L + 10*V + E,
        label(Vars).