/* Le compilateur de problemes cryptarithmetiques */

:- dynamic(sol/1).

/* Auxiliaires */
rev(L, R) :- revl(L, [], R).

revl([], R, R).
revl([X|S], T, R) :- revl(S, [X|T], R).

concat([], X, X).
concat([A | B], C, [A | D]) :- concat(B, C, D).

/* member(X, [X|S]) :- !.
member(X, [Y|S]) :- member(X, S). */

/* pour l'exe'cution ... */
tous_diff([]).
tous_diff([A|S]) :- not(member(A, S)), tous_diff(S).

chiffre(0). chiffre(1). chiffre(2). chiffre(3). chiffre(4). 
chiffre(5). chiffre(6). chiffre(7). chiffre(8). chiffre(9). 

col(Reste_p, Ch1, Ch2, Chr, Reste_n) :- chiffre(Ch1), chiffre(Ch2), 
		Somme is Reste_p+Ch1+Ch2, 
		Reste_n is Somme//10, Chr is Somme mod 10.

/* Queue de la clause */
csq(U, V, W, C) :-  rev(U, RU), rev(V, RV), rev(W, RW), rcsq(RU, RV, RW, C).

rcsq([DU|SU], [DV|SV], [DW|SW], ((col(0, DU, DV, DW, R), CS))) :-
	rcss(SU, SV, SW, R, CS).

rcss([], [], [PW], R, ((col(R, 0, 0, PW, 0), not(PW = 0)))). /* arret 1 */
rcss([PU], [PV], [PW], R, ((col(R, PU, PV, PW, 0), not(PW = 0)))). /*arret2*/
rcss([NU|SU], [NV|SV], [NW|SW], R, ((col(R, NU, NV, NW, RN), CS))) :-
	rcss(SU, SV, SW, RN, CS). /* avec creation d'une nouvelle var ds RN */

/* Le predicat-maitre */
csol(U, V, W, ((sol(LV) :- (Q, tous_diff(LV))))) :-  
	concat(U, V, UV), concat(UV, W, UVW), sort(UVW, LV), csq(U, V, W, Q).

/* Auxiliaires pour la jolie impression */

long([], 0).
long([X|S], K) :- long(S, H), K is H+1.

ligne([]) :- nl.
ligne([X|S]) :- V is X, write(V), ligne(S).

trait(0):- !, nl.
trait(N) :- write('-'), M is N-1, trait(M).

/* La jolie impression */

ijoli(D, U, V, W) :- long(U, H), long(V, K), long(W, L),
			iijoli(D, U, V, W, H, K, L).

iijoli(D, U, V, W, H, H, H) :-  /* les trois de meme longueur */
		      nl, tab(D), tab(2), ligne(U), 
		      tab(D), write('+ '), ligne(V),
		      tab(D), K is H+2, trait(K),
		      tab(D), tab(2), ligne(W).

iijoli(D, U, V, W, H, H, L) :- L is H+1, !, /* un de plus pour la somme */
		      nl, tab(D), tab(2), ligne(U), 
		      tab(D), write('+ '), ligne(V),
		      tab(D), K is H+2, trait(K),
		      tab(D), tab(1), ligne(W).

iijoli(D, U, V, W, H, K, K) :- H < K, !, DH is K-H,
		      nl, tab(D), tab(2), tab(DH), ligne(U), 
		      tab(D), write('+ '), ligne(V),
		      tab(D), T is K+2, trait(T),
		      tab(D), tab(2), ligne(W).

iijoli(D, U, V, W, H, K, H) :- K < H, !, DK is H-K,
		      nl, tab(D), tab(2), ligne(U), 
		      tab(D), write('+ '), tab(DK), ligne(V),
		      tab(D), T is H+1, trait(T),
		      tab(D), tab(1), ligne(W).

/* Exe'cution avec jolie impression */

auvol(U, V, W) :- csol(U,V,W,(T :- Q)), assert((T :- Q)), 
		  call(T), ijoli(15, U,V,W).

/* Essais */

av1 :- auvol([S,E,N,D], [M,O,R,E], [M,O,N,E,Y]).
av2 :- auvol([B,I,G], [B,O,Y], [M,A,N]).
av3 :- auvol([D,O,N,A,L,D], [G,E,R,A,L,D], [R,O,B,E,R,T]).


