:-use_module(library(clpfd)).

solve_clp(Sol):-
	Sol=[S,E,N,D,M,O,R,Y],

	domain([E,N,D,O,R,Y],0,9),
	domain([S,M],1,9),

		  1000*S + 100*E + 10*N + D +
		  1000*M + 100*O + 10*R + E #=
	10000*M + 1000*O + 100*N + 10*E + Y,
	all_different([S,E,N,D,M,O,R,Y]),

	labeling([],Sol).

solve_naive([S,E,N,D,M,O,R,Y]):-
	Digits1_9 = [1,2,3,4,5,6,7,8,9],
	Digits0_9 = [0|Digits1_9],
	member(S, Digits1_9),
	member(E, Digits0_9), E\=S,
	member(N, Digits0_9), N\=S, N\=E,
	member(D, Digits0_9), D\=S, D\=E, D\=N,
	member(M, Digits1_9), M\=S, M\=E, M\=N, M\=D,
	member(O, Digits0_9), O\=S, O\=E, O\=N, O\=D, O\=M,
	member(R, Digits0_9), R\=S, R\=E, R\=N, R\=D, R\=M, R\=O,
	member(Y, Digits0_9), Y\=S, Y\=E, Y\=N, Y\=D, Y\=M, Y\=O, Y\=R,
	          1000*S + 100*E + 10*N + D +
	          1000*M + 100*O + 10*R + E =:=
	10000*M + 1000*O + 100*N + 10*E + Y.

solve_better([S,E,N,D,M,O,R,Y]):-
	% D+E = 10*P1+Y
	member(D,[0,1,2,3,4,5,6,7,8,9]),
	member(E,[0,1,2,3,4,5,6,7,8,9]), E\=D,
	Y is (D+E) mod 10, Y\=D, Y\=E,
	P1 is (D+E) // 10,

	% N+R+P1 = 10*P2+E
	member(N,[0,1,2,3,4,5,6,7,8,9]), N\=D, N\=E, N\=Y,
	R is (10+E-N-P1) mod 10, R\=D, R\=E, R\=Y, R\=N,
	P2 is (N+R+P1) // 10,

	% E+O+P2 = 10*P3+N
	O is (10+N-E-P2) mod 10, O\=D, O\=E, O\=Y, O\=N, O\=R,
	P3 is (E+O+P2) // 10,

	% S+M+P3 = 10*M+O
	member(M,[1,2,3,4,5,6,7,8,9]), M\=D, M\=E, M\=Y, M\=N, M\=R, M\=O,
	S is 9*M+O-P3, S>0,S<10, S\=D, S\=E, S\=Y, S\=N, S\=R, S\=O, S\=M.

member(X,[X|_]).
member(X,[_|T]):- member(X,T).


less_then(A,B):-
	fd_global(a2b(A,B),no_state,[min(A)]),
	fd_global(b2a(A,B),no_state,[max(B)]).

diff(A,B):-
	fd_global(diff(A,B),no_state,[val(A)]),
	fd_global(diff(B,A),no_state,[val(B)]).

all_diff(List):-
	start_all_diff(List,List).
start_all_diff([],_).
start_all_diff([H|T],List):-
	fd_global(all_diff(H,T,List),no_state,[val(H)]),
	start_all_diff(T,List).

exactly(0, [], _X).
exactly(N, [Y|L], X) :-
	X #= Y #<=> B,
	N #= M+B,
	exactly(M, L, X).

queensBT(N,Queens):-
	length(Queens,N),
	gen_list(1,N,Positions),
	gen_queens(Queens,[],Positions).

gen_queens([],_,_).
gen_queens([Q|Rest],Assigned,Positions):-
	member(Q,Positions),
	no_attack(Assigned,Q,1),
	gen_queens(Rest,[Q|Assigned],Positions).

gen_list(N,N,[N]).
gen_list(I,N,[I|Rest]):-
	I<N,NextI is I+1,
	gen_list(NextI,N,Rest).

no_attack([],_,_).
no_attack([Q1|Rest],Q,Dist):-
	Q1\=Q, Q1+Dist=\=Q, Q1-Dist=\=Q,
	NextDist is Dist+1,
	no_attack(Rest,Q,NextDist).

% N-queens using binary inequalities
queensCLP(N,Queens):-
	length(Queens,N),
	domain(Queens,1,N),
	all_different(Queens),
	constraint_all(Queens),
	labeling([ff],Queens).

constraint_all([]).
constraint_all([Q|Qs]):-
	constraint_queens(Qs,Q,1),
	constraint_all(Qs).

constraint_queens([],_,_).
constraint_queens([Q2|Qs],Q1,I):-
	Q1#\=Q2+I, Q1#\=Q2-I,
	I1 is I+1,
	constraint_queens(Qs,Q1,I1).


:-multifile clpfd:dispatch_global/4.

clpfd:dispatch_global(a2b(A,B),S,S,Actions):-
	fd_min(A,MinA), fd_max(A,MaxA), fd_min(B,MinB),
	(MaxA<MinB ->
	    Actions = [exit]
	;
	    LowerBoundB is MinA+1,
	    Actions = [B in LowerBoundB..sup]
	).
clpfd:dispatch_global(b2a(A,B),S,S,Actions):-
	fd_max(A,MaxA), fd_min(B,MinB), fd_max(B,MaxB),
	(MaxA<MinB ->
	    Actions = [exit]
	;
	    UpperBoundA is MaxB-1,
	    Actions = [A in inf..UpperBoundA]
	).

clpfd:dispatch_global(diff(X,Y),S,S,Actions):-
	(ground(X) ->
	    fd_set(Y,SetY),
	    fdset_del_element(SetY,X,NewSetY),
	    Actions = [exit, Y in_set NewSetY]
	;
	    Actions = []
	).

clpfd:dispatch_global(all_diff(X,Pointer,List),S,S,Actions):-
	(ground(X) ->
	    filter_diff(List,X,Pointer, Actions)
	;
	    Actions = []
	).

filter_diff([],_X,_Pointer, [exit]).
filter_diff([Y|T],X,Pointer, Actions):-
	(T==Pointer ->
	    Actions = RestActions
	;
	    fd_set(Y,SetY),
	    fdset_del_element(SetY,X,NewSetY),
	    Actions = [Y in_set NewSetY | RestActions]
	),!,
	filter_diff(T,X,Pointer, RestActions).



