/* SEND+MORE=MONEY puzzle in SWI Prolog Solve the alphametic problem SEND+MORE=MONEY using distinct digits for the letters. Some CLP and non-CLP approaches. Model created by Hakan Kjellerstrand, hakank@gmail.com See also my SWI Prolog page: http://www.hakank.org/swi_prolog/ */ :- use_module(library(clpfd)). :- use_module(hakank_utils). % % Plain CLP. 0.003s % go :- send_more_money(Digits), writeln(digits_before=Digits), list_domains(Digits,Domains), writeln(domains=Domains), labeling([ff],Digits), writeln(Digits), nl. % % using scalar_product/4: 0.007s % go2 :- send_more_money_scalar_product(Digits), writeln(Digits), list_domains(Digits,Domains), writeln(domains=Domains), labeling([ff],Digits), writeln(Digits), nl. % % With carry: 0.005s % go3 :- send_more_money_with_carry(Digits, Carry), writeln(digits=Digits), writeln(carry=Carry), append(Digits,Carry, Vars), labeling([ff],Vars), writeln(digits=Digits), writeln(carry=Carry), nl. % % No CLPFD, using select. TOO SLOW! % go4 :- time(send_more_money_no_cp1(Digits)), writeln(Digits), nl. % % No CLPFD, using assign/select. 1.7s. % go5 :- time(send_more_money_no_cp2(Digits)), writeln(Digits), nl. % % No CLPFD, using permutation/2. % go6 :- time(send_more_money_permutation(Digits)), writeln(Digits), nl. % % Plain CLP. % send_more_money(Digits) :- Digits = [S,E,N,D,M,O,R,Y], Digits ins 0..9, all_distinct(Digits), S #> 0, M #> 0, 1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E #= 10000*M + 1000*O + 100*N + 10*E + Y. % % Using scalar_product. % send_more_money_scalar_product(Digits) :- Digits = [S,E,N,D,M,O,R,Y], Digits ins 0..9, all_distinct(Digits), S #> 0, M #> 0, Base4 = [1000,100,10,1], Base5 = [10000,1000,100,10,1], scalar_product(Base4, [S,E,N,D], #=, SEND), scalar_product(Base4, [M,O,R,E], #=, MORE), scalar_product(Base5, [M,O,N,E,Y], #= , MONEY), SEND + MORE #= MONEY. % % With carry % % C4 C3 C2 C1 % S E N D % + M O R E % --------------- % = M O N E Y % send_more_money_with_carry(Digits, Carry) :- Digits = [S,E,N,D,M,O,R,Y], Digits ins 0..9, Carry = [C1,C2,C3,C4], Carry ins 0..1, all_distinct(Digits), S #> 0, M #> 0, C4 #= M, C3 + S + M #= O + 10 * C4, C2 + E + O #= N + 10 * C3, C1 + N + R #= E + 10 * C2, D + E #= Y + 10 * C1. % % Without CLP, using select. TOO SLOW % send_more_money_no_cp1(Digits) :- Digits = [S,E,N,D,M,O,R,Y], between(0,9,S), select(S,Digits,Rest1), S #\= 0, between(0,9,E), select(E,Rest1,Rest2), between(0,9,N) , select(N,Rest2,Rest3), between(0,9,D), select(D,Rest3,Rest4), between(0,9,M), select(M,Rest4,Rest5), M #\= 0, between(0,9,O), select(O,Rest5,Rest6), between(0,9,R), select(R,Rest6,Rest7), between(0,9,Y), select(Y,Rest7,_Rest8), (S * 1000 + E * 100 + N * 10 + D) + (M * 1000 + O * 100 + R * 10 + E) #= (M * 10000 + O * 1000 + N * 100 + E * 10 + Y ). % % Variant where the selects are moved to assign/2 % Much faster than send_more_money_no_cp2: 1.7s % send_more_money_no_cp2(Digits) :- Digits = [S,E,N,D,M,O,R,Y], assign([0,1,2,3,4,5,6,7,8,9],Digits), S \= 0, M \= 0, (S * 1000 + E * 100 + N * 10 + D) + (M * 1000 + O * 100 + R * 10 + E) =:= (M * 10000 + O * 1000 + N * 100 + E * 10 + Y ). % % assign( Digits, Vars) % Assign chosen distinct digits from list Digits to variables in list Vars % assign(_,[]). assign(Digs,[D|Vars]) :- select(D, Digs,Digs1), assign(Digs1,Vars). % % Without CLP, using permutation/2: ~3.0s % send_more_money_permutation(Digits2) :- Digits = [S,E,N,D,M,O,R,Y, A,B], permutation([0,1,2,3,4,5,6,7,8,9],Digits), A < B, % symmetry breaking of the two unused digits S > 0, M #> 0, (S * 1000 + E * 100 + N * 10 + D) + (M * 1000 + O * 100 + R * 10 + E) =:= (M * 10000 + O * 1000 + N * 100 + E * 10 + Y), Digits2 = [S,E,N,D,M,O,R,Y].