bsend.pl

PRl教学程序 PRl教学程序 PRl教学程序

/*-------------------------------------------------------------------------*/
/* Benchmark (Boolean)                                                     */
/*                                                                         */
/* Name           : bsend.pl                                               */
/* Title          : crypt-arithmetic                                       */
/* Original Source: Daniel Diaz - INRIA France                             */
/* Adapted by     : Daniel Diaz for CLP(FD)                                */
/* Date           : January 1993                                           */
/*                                                                         */
/* Solve the operation:                                                    */
/*                                                                         */
/*      S E N D                                                            */
/*  +   M O R E                                                            */
/*  -----------                                                            */
/*  = M O N E Y                                                            */
/*                                                                         */
/* (resolution by column)                                                  */
/* The digit of each letter is coded in binary on 4 bits (dcb). The order  */
/* for labeling is very relevant for efficiency.                           */
/*                                                                         */
/* Solution:                                                               */
/*  [S,E,N,D,M,O,R,Y]                                                      */
/*  [[1,0,0,1],[0,1,0,1],[0,1,1,0],[0,1,1,1],[0,0,0,1],[0,0,0,0],[1,0,0,0],*/
/*   [0,0,1,0]]                                                            */
/* ie:                                                                     */
/*  [9,5,6,7,1,0,8,2]                                                      */
/*-------------------------------------------------------------------------*/

go:-
    statistics(runtime,_),
    top,
    statistics(runtime,[_,Y]),
    write('time : '), write(Y), nl.

top:-	
    (bsend(A), 
     write(A), nl,
     fail
     ; 
     write('No more solutions'), nl).

bsend(A):-
	A=[S,E,N,D,M,O,R,Y],
	dcb_digit(S),
	dcb_digit(E),
	dcb_digit(N),
	dcb_digit(D),
	dcb_digit(M),
	dcb_digit(O),
	dcb_digit(R),
	dcb_digit(Y),

	diff0(S),
	diff0(M),

	all_dcb_digit_diff(A),

	LC=[C1,C2,C3,C4],
	Z=[0,0,0,0],
	dcb_add(0, D,E,Y,C1),
	dcb_add(C1,N,R,E,C2),
	dcb_add(C2,E,O,N,C3),
	dcb_add(C3,S,M,O,C4),
	dcb_add(C4,Z,Z,M,0),
	!,
        lists_labeling(A),
	fd_labeling(LC).

dcb_digit(D):- 
	D=[B3,B2,B1,_],
	B3 #=> #\ B2 #/\ #\ B1.

diff0([B3,B2,B1,B0]):-
	B3 #\/ B2 #\/ B1 #\/ B0.

all_dcb_digit_diff([]).

all_dcb_digit_diff([X|L]):-
	diff_of(L,X),
	all_dcb_digit_diff(L).

diff_of([],_).

diff_of([Y|L],X):-
	dcb_digit_diff(X,Y),
	diff_of(L,X).

dcb_digit_diff([X3,X2,X1,X0],[Y3,Y2,Y1,Y0]):-
	#\ ((X3 #<=> Y3) #/\ (X2 #<=> Y2) #/\ (X1 #<=> Y1) #/\ (X0 #<=> Y0)).

dcb_add(CI,[X3,X2,X1,X0],[Y3,Y2,Y1,Y0],[Z3,Z2,Z1,Z0],CO):-
	full_add(CI,X0,Y0,Z0,C1),
	full_add(C1,X1,Y1,I1,C2),
	full_add(C2,X2,Y2,I2,C3),
	full_add(C3,X3,Y3,I3,C4),
	I2 #\/ I1 #<=> I12,
	I3 #/\ I12 #<=> I123,
	C4 #\/ I123 #<=> Hex,
	half_add(I1,Hex,Z1,D2),
	full_add(D2,I2,Hex,Z2,D3),
	half_add(D3,I3,Z3,D4),
	C4 #\/ D4 #<=> CO.

full_add(CI,X,Y,Z,CO):-
	half_add(X,Y,Z1,C1),
	half_add(CI,Z1,Z,C2),
	C1 #\/ C2 #<=> CO.

half_add(X,Y,Z,CO):-
	X #/\ Y #<=> CO,
	X #\ Y #<=> Z.

lists_labeling([X|Xs]):-
    labeling(X),
    lists_labeling(Xs).
lists_labeling([]).