Cryptarithmetic multiplication, any digits. Prolog

Question

Im trying to solve this Cryptarithmetic puzzle:

in which "*" represents any digit.

This is the code that i came up with so far.

permutation(Xs,[Z|Zs]) :-
    delete(Z,Xs,Ys),
    permutation(Ys,Zs).

delete(X,[X|Xs],Xs).
delete(X,[Y|Ys],[Y|Zs]) :-
    delete(X,Ys,Zs).

ca(A, B, C, D, E, F, G, H, I, J) :-
    permutation([1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
               [A, B, C, D, E, F, G, H, I, J]),
               (A*10000+B*1000+C*100+D*10+E*1) * (A * 1)
               =:=
               (_ * 100000 + _ * 10000 + H * 1000 + _ * 100 + _ * 10 + _ * 1).

I am fully aware that Prolog cannot just simply solve this equation using the _ operator.

What I'm trying to figure out is how to implement those unimportant digits which are represented in my code as single underscores.

Thanks for your help.

Answer 1

Solved with clpfd as suggested in the comments (try this video to learn clpfd):

:- use_module(library(clpfd)).

% relates numbers to their digits, e.g. number_digits(123, [1,2,3]).
number_digits(0, []).
number_digits(Num, [D|Ds]) :-
    D in 0..9,
    Num #= D*10^Exp + Num0,
    length(Ds, Exp),
    number_digits(Num0, Ds).

puzzle(Digits) :-
    Digits = [A,B,C,D,E,F,G,H],
    
    number_digits(Num1, [A,B,C,D,E]), 
    number_digits(Num2, [F,G,A]),
    
    Num3 #= Num1 * A,  
    number_digits(Num3, [_,_,H,_,_,_]),
    
    Num4 #= Num1 * G,
    number_digits(Num4, [B,B,_,_,_]),
    
    Num5 #= Num1 * F,
    number_digits(Num5, [_,_,H,_,_,_]),
    
    Num6 #= Num3 + Num4*10 + Num5*100,    
    number_digits(Num6, [_,F,_,_,_,D,_,_]),
    
    all_distinct(Digits),
    label(Digits).

Try on SWIPL: https://swish.swi-prolog.org/p/NSmyRcuA.pl

A query results in the unique solution:

?- puzzle(Digits).
Digits = [4, 9, 6, 0, 7, 5, 2, 8];

Answer 2

Write

.....
   mult1( [E,D,C,B,A], A, X), X= [_,_,_,H,_,_], 
   mult1( [E,D,C,B,A], G, Y), Y= [_,_,_,B,B], 
   mult1( [E,D,C,B,A], F, Z), Z= [_,_,_,H,_,_], 
   sum2( X, [0|Y], S), 
   sum2( S, [0,0|Z],             [_,_,D,_,_,_,F,_] ).

Now implement mult1 and sum2 to make it work.

To make it more efficient, make the selections with

.....
   mselect( [A,B,C,D,E,H], [0,1,2,3,4,5,6,7,8,9], R1),
   .....
   mselect( [G], R1, R2),
   .....
   mselect( [F], R2, _),
   .....

% mselect/3 defined as
mselect( [A|B], C, R) :- select(A,C,D), mselect(B,D,R).
mselect( [], R, R).

We don't need no I and J at all. We also don't need F and G for the first multiplication, and no F for the second.

All the digits will be different, by construction.

Answer 3

A solution using constraints:

:- op(150, fx, #).

base_(B, D, S0, S) :-
    #D #>= 0,
    #D #< #B,
    #S #= #D+ #B* #S0.

puzzle(M, N) :-
    foldl(base_(10), [A,B,_,D,_], 0, M), #A #\= 0,
    foldl(base_(10), [F,G,A], 0, N), #F #\= 0,

    foldl(base_(10), [D0,_,H,_,_,_], 0, T0), #D0 #\= 0,
    #T0 #= #M* #A,
    foldl(base_(10), [B,B,_,_,_], 0, T1), #B #\= 0,
    #T1 #= #M* #G,
    foldl(base_(10), [D2,_,H,_,_,_], 0, T2), #D2 #\= 0,
    #T2 #= #M* #F,

    foldl(base_(10), [D3,F,_,_,_,D,_,_], 0, T3), #D3 #\= 0,
    #T3 #= #M* #N.

    % #T3 #= #T0+ #T1*10+ #T2*100. % Redundant constraints.

?- puzzle(M, N), labeling([ff], [M,N]).
   M = 49605, N = 524
;  M = 49607, N = 524
;  M = 49611, N = 524
;  false.