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

affecter([],Vals).
affecter([X|Vars],Vals) :- select(X,Vals,L), affecter(Vars,L).

somme(S,E,N,D,M,O,R,Y) :- N1 is 1000*S+100*E+10*N+D,
                        N2 is 1000*M+100*O+10*R+E,
                        N3 is 10000*M+1000*O+100*N+10*E+Y,
                        N3 is N1+N2. 

solution([S,E,N,D],[M,O,R,E],[M,O,N,E,Y]) :- affecter([S,E,N,D,M,O,R,Y],[0,1,2,3,4,5,6,7,8,9]), M > 0, S > 0, somme(S,E,N,D,M,O,R,Y).

% solution([S,E,N,D],[M,O,R,E],[M,O,N,E,Y]) :- affecter([S,E,N,D,M,O,R,Y],[9,5,6,7,1,0,8,2,3]), M > 0, S > 0, somme(S,E,N,D,M,O,R,Y).

% les variables apparaissant souvent sont assignees en premier
% solution([S,E,N,D],[M,O,R,E],[M,O,N,E,Y]) :- affecter([E,M,O,N,S,D,R,Y],[0,1,2,3,4,5,6,7,8,9]), M > 0, S > 0, somme(S,E,N,D,M,O,R,Y).

% utiliser les retenues pour guider la recherche
%              M                is              R4,
%              O  +  10  *  R4  is  M  +  S  +  R3,
%              N  +  10  *  R3  is  O  +  E  +  R2,
%              E  +  10  *  R2  is  R  +  N  +  R1,
%              Y  +  10  *  R1  is  E  +  D,