:- module(_,_).

% :- use_package(clpq).
:- use_package(clpr).

% --- Basic aritmetic ----------------------------
%% Query examples:

 %% hp(3, 4, Z).  
 %% hp(X, Y, f(3,4)).  
 %% hp(X, Y, Z).

 %% hc(3, 4, Z).  
 %% hc(X, Y, f(3,4)).  
 %% hc(X, Y, Z).

 %% ap(3, 4, Z).
 %% ap(X, 4, 7).

 %% ac(3, 4, Z).
 %% ac(X, 4, 7).
 %% ac(X, Y, 7).

hp(X,Y,Z) :- Z = f(X,Y).

hc(X,Y,Z) :- Z = f(X,Y).

ap(X,Y,Z) :- Z is X + Y.
ac(X,Y,Z) :- Z .=. X+Y.

% --- Constrain and generate ----------------------------
%% solution_gen_test_prolog(X, Y, Z).
%% solution_gen_test_clp(X, Y, Z).
%% solution_cons_gen_prolog(X, Y, Z).
%% solution_cons_gen_clp(X, Y, Z).

solution_gen_test_prolog(X, Y, Z) :-
    p(X),
    p(Y),
    p(Z),
    prolog_test(X, Y, Z).

prolog_test(X, Y, Z) :-  Y is X + 1, Z is Y + 1.

p(11). p(3). p(7). p(16). p(15). p(14).

solution_gen_test_clp(X, Y, Z) :-
    p(X),
    p(Y),
    p(Z),
    clp_test(X, Y, Z).

clp_test(X, Y, Z) :-  Y .=. X + 1, Z .=. Y + 1.

solution_cons_gen_prolog(X, Y, Z) :-
    prolog_test(X, Y, Z),
    p(X),
    p(Y),
    p(Z).

solution_cons_gen_clp(X, Y, Z) :-
    clp_test(X, Y, Z), 
    p(X),
    p(Y),
    p(Z).


:- discontiguous p/1.
%% Making the search space a little larger:
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% 
%% p(11). p(3). p(7). p(16). p(15). p(14).
%% 
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).
%% p(0).  p(0). p(0). p(0).  p(0).  p(0). p(0).  p(0). p(0). p(0).  p(0).  p(0).

example1(X, _Y) :- X .=. 4 + 3.
example2(X, Y)  :- X .=. 4 + 3, Y = f(X, _Z).
example3(X, Y)  :- X + Y .=<. 4, Y .>=. 4, X .>=. 0.
example4(X, Y)  :- X + Y .=<. 4, Y .>=. 4, X .>=. 0.
example5(X, Y)  :- Y .>=. 4, X .>=. 0.


%% prod([2, 3], [4, 5], K).   
%% prod([2, 3], [5, X2], 22). 
%% prod([2, 7, 3], [Vx, Vy, Vz], 0). 
%% prod([3,1],[X,Y],5), prod([1,8],[X,Y],3).
%% prod([Y,2,3],[4,X,6],32).

prod([], [], Resul) :- 
	Resul .=. 0.
prod([X|Xs], [Y|Ys], Resul) :-
	Resul .=. X * Y + Rest,
	prod(Xs, Ys, Rest).

% CLPR:

pprod([], [], 0).
pprod([X|Xs], [Y|Ys], X * Y + Rest) :-
	pprod(Xs, Ys, Rest).

%% prod([X|Xs],[Y|Ys],Resul) :-
%% 	prod(Xs,Ys,Rest),
%% 	Resul is X*Y+Rest.

%% system([X, Y], [[3, 1],[1, 8]],[5, 3]).
%% system([37/23, 4/23], [[3, 1],[1, 8]],[X, Y]).

system(_Vars, [], []). 
system(Vars, [Co|Coefs], [Ind|Indeps]) :- 
    prod(Vars, Co, Ind),
    system(Vars, Coefs, Indeps).

% Nondeterministic (several possible intervals):

rx(X) :- X .>. 3, X .<. 4.
rx(X) :- X .>. 5, X .<. 7.

foo(X,Y) :- rx(X), Y .>. 0, Y .<. 6, X - Y .=. 1.


%% X*X + 2*X + 1 .=. 0.

%% cossin(X,Y).

cossin(X,Y) :- X .=. sin(cos(Y)), Y .=. 2 + Y * 3.

%% X+Y .=<. 4, Y .>=.4, X .>=. 0.

%% ?- plfib(11,Y).
%% ?- fib(11,Y).
%% ?- plfib(X,89).
%% ?- fib(X,89).

plfib(0,0).
plfib(1,1).
plfib(N,R) :-
    N > 1, 
    N1 is N-1,
    N2 is N-2,
    plfib(N1,F1),
    plfib(N2,F2),
    R is F1+F2.

fib(N,N) :- N .=. 0.
fib(N,N) :- N .=. 1.
fib(N,R) :- 
    N .>. 1,
    F1 .>=. 0, 
    F2 .>=. 0, 
    N1 .=. N - 1,
    N2 .=. N - 2,
    fib(N1,F1),
    fib(N2,F2),
    R .=. F1 + F2.

%----------------------------------------
% plfib(3, X).
%
% fib(3, X).
%----------------------------------------

c_add(c(Re1,Im1), c(Re2,Im2), c(Re12,Im12)) :- 
	Re12 .=. Re1+Re2,
	Im12 .=. Im1+Im2.

c_mult(c(Re1, Im1), c(Re2, Im2), c(Re3, Im3)) :-
      Re3 .=. Re1 * Re2 - Im1 * Im2,
      Im3 .=. Re1 * Im2 + Re2 * Im1.

circuit(resistor(R), V, I, _W) :- 
    c_mult(I, c(R, 0), V).

circuit(inductor(L), V, I, W) :- 
    Im .=. W * L,
    c_mult(I, c(0, Im), V).

circuit(capacitor(C), V, I, W) :- 
    Im .=. -1 / (W * C),
    c_mult(I, c(0, Im), V).

% Putting these after the components, so that synthesis is directed
circuit(parallel(N1, N2), V, I, W) :-
       c_add(I1, I2, I),
       circuit(N1, V, I1, W),
       circuit(N2, V, I2, W).

circuit(series(N1, N2), V, I, W) :-
       c_add(V1, V2, V),
       circuit(N1, V1, I, W),
       circuit(N2, V2, I, W).


/*
?- circuit(parallel(inductor(0.073), 
                    series(capacitor(C), resistor(R))), 
           c(4.5, 0), c(0.65, 0), 2400).
?- circuit(C, 
           c(4.5, 0), c(0.65, 0), 2400).
*/

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Queens 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% In Prolog. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

plqueens(N, Qs) :- 
    plqueens_list(N, Ns), 
    plqueens_(Ns, [], Qs).

plqueens_([], Qs, Qs).
plqueens_(Unplaced, Placed, Qs) :-
    selectq(Unplaced, Q, NewUnplaced), 
    pl_no_attack(Placed, Q, 1),
    plqueens_(NewUnplaced, [Q|Placed], Qs).

pl_no_attack([], _Queen, _Nb).
pl_no_attack([Y|Ys], Queen, Nb) :-
    Queen =\= Y + Nb, 
    Queen =\= Y - Nb, 
    Nb1 is Nb + 1,
    pl_no_attack(Ys, Queen, Nb1).

selectq([X|Ys], X, Ys).
selectq([Y|Ys], X, [Y|Zs]) :-
    selectq(Ys, X, Zs).

plqueens_list(0, []).
plqueens_list(N, [N|Ns]) :-
    N > 0, N1 is N - 1, plqueens_list(N1, Ns).

%% plqueens_list(N, L) :- plqueens_list_(N, [], L). 
%% 
%% plqueens_list_(0, L, L).
%% plqueens_list_(N, Ns, L) :- 
%%        N > 0, 
%%        N1 is N - 1, 
%%        plqueens_list_(N1, [N|Ns], L).

%% ?- between(1,100,N),clock(plqueens(N,L)), fail.
%% Computed plqueens(5,_418) in 0.00004 seconds.
%% Computed plqueens(22,_418) in 4.46143 seconds.
%% Computed plqueens(23,_418) in 0.081406 seconds.
%% Computed plqueens(24,_418) in 1.297789 seconds.
%% Computed plqueens(27,_418) in 1.904108 seconds.
%% Computed plqueens(28,_418) in 13.148916999999999 seconds.
%% Computed plqueens(29,_418) in 6.974818 seconds.
%% Computed plqueens(30,_418  C-c C-c)

%% ?- between(1,100,N),clock_all(plqueens(N,L)), fail.
%% Computed for plqueens(1,_428) -> 1 sols in 0.000059 seconds.
%% Computed for plqueens(2,_428) -> 0 sols in 0.000034 seconds.
%% Computed for plqueens(3,_428) -> 0 sols in 0.000032 seconds.
%% Computed for plqueens(4,_428) -> 2 sols in 0.000044999999999999996 seconds.
%% Computed for plqueens(5,_428) -> 10 sols in 0.00008400000000000001 seconds.
%% Computed for plqueens(6,_428) -> 4 sols in 0.00016800000000000002 seconds.
%% Computed for plqueens(7,_428) -> 40 sols in 0.000798 seconds.
%% Computed for plqueens(8,_428) -> 92 sols in 0.002096 seconds.
%% Computed for plqueens(9,_428) -> 352 sols in 0.007731 seconds.
%% Computed for plqueens(10,_428) -> 724 sols in 0.027948 seconds.
%% Computed for plqueens(11,_428) -> 2680 sols in 0.137737 seconds.
%% Computed for plqueens(12,_428) -> 14200 sols in 0.7901079999999999 seconds.
%% Computed for plqueens(13,_149) -> 73712 sols in 4.877805 seconds.
%% Computed for plqueens(14,_149) -> 365596 sols in 31.401280999999997 seconds.

%% CLP version %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

queens(N, Qs) :- 
    constrain_values(N, N, Qs),
    place_queens(N, Qs).

constrain_values(0, _N, []).
constrain_values(I, N, [X|Xs]) :-
    I .>. 0,
    X .>. 0, X .=<. N, % All queens between 0 and N
    I1 .=. I - 1,
    constrain_values(I1, N, Xs), no_attack(Xs, X, 1).

no_attack([], _Queen, _Nb).
no_attack([Y|Ys], Queen, Nb) :-
    Queen .<>. Y + Nb,
    Queen .<>. Y - Nb,
    Nb1 .=. Nb + 1,
    no_attack(Ys, Queen, Nb1).

place_queens(0, _).
place_queens(N, Q) :- 
    N .>. 0, 
    memberq(N, Q), 
    N1 .=. N - 1, 
    place_queens(N1, Q).

memberq(X, [X|_]).
memberq(X, [_|Xs]) :- memberq(X, Xs).

%% Somewhat nicer with clpq?
%% queens(4, Qs).
%% constrain_values(4, 4, Qs)
%% constrain_values(4, 4, Qs), Qs = [3,1|OQs].
%% constrain_values(4, 4, Qs), Qs = [3,2|OQs]. % Bad stated rejected using constraint consistency
%% member(4, [A, B, C, D]).

%% Computed queens(5,_414) in 0.000357 seconds.
%% Computed queens(16,_414) in 1.094156 seconds.
%% Computed queens(17,_414) in 0.701433 seconds.
%% Computed queens(18,_414) in 5.758049 seconds.
%% Computed queens(19,_414) in 0.42109800000000003 seconds.
%% Computed queens(20,_414  C-c C-c)

%% ?- between(1,100,N),clock(queens(N,L)), fail.

%% ?- between(1,100,N),clock_all(queens(N,L)), fail.
%% Computed for queens(1,_428) -> 1 sols in 0.00010899999999999999 seconds.
%% Computed for queens(2,_428) -> 0 sols in 0.000111 seconds.
%% Computed for queens(3,_428) -> 0 sols in 0.000185 seconds.
%% Computed for queens(4,_428) -> 2 sols in 0.000442 seconds.
%% Computed for queens(5,_428) -> 10 sols in 0.001373 seconds.
%% Computed for queens(6,_428) -> 4 sols in 0.005176 seconds.
%% Computed for queens(7,_428) -> 40 sols in 0.013832 seconds.
%% Computed for queens(8,_428) -> 92 sols in 0.056472 seconds.
%% Computed for queens(9,_428) -> 352 sols in 0.270452 seconds.
%% Computed for queens(10,_428) -> 724 sols in 1.335577 seconds.
%% Computed for queens(11,_428) -> 2680 sols in 7.613237 seconds.
%% Computed for queens(12,_149) -> 14200 sols in 47.978779 seconds.

 %% no_attack([], _Queen, _Nb).
 %% no_attack([Y|Ys], Queen, Nb) :-
 %%         % Queen .<>. Y + Nb, % In Ciao!!!
 %%         abs(Queen - (Y + Nb)) .>. 0,  % Queen =\= Y + Nb
 %%         abs(Queen - (Y - Nb)) .>. 0,  % Queen =\= Y - Nb
 %% 	Nb1 .=. Nb + 1,
 %%         no_attack(Ys, Queen, Nb1).


%% pl_place_queens(0, _).
%% pl_place_queens(N, Q) :- 
%%     N > 0, 
%%     memberq(N, Q), 
%%     N1 is N - 1, 
%%     pl_place_queens(N1, Q).

% between(1,100,N),clock(queens_2(N,L)), fail.

clock(Q) :-
    write('Computed '), write(Q), 
    statistics(walltime,_),
    call(Q),
    statistics(walltime,[_,T]),
    !,
    S is T/1000,
    write(' in '), write(S), write(' seconds.'), nl.

clock_all(Q) :-
    write('Computed for '), write(Q), write(' -> '),
    statistics(walltime,_),
    findall(Q,Q,Sols),
    statistics(walltime,[_,T]),
    length(Sols,L),
    S is T/1000,
    write(L), write(' sols in '), write(S), write(' seconds.'), nl.

%% CLP written as in Prolog %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

plc_queens(N, Qs) :- 
    plc_queens_list(N, Ns), 
    plc_queens_(Ns, [], Qs).

plc_queens_([], Qs, Qs).
plc_queens_(Unplaced, Placed, Qs) :-
    selectq(Unplaced, Q, NewUnplaced), 
    no_attack(Placed, Q, 1),
    plc_queens_(NewUnplaced, [Q|Placed], Qs).

plc_queens_list(0, []).
plc_queens_list(N, [N|Ns]) :-
    N .>. 0, N1 .=. N - 1, plc_queens_list(N1, Ns).


%% ?- between(1,100,N),clock_all(plc_queens(N,L)), fail.
%% Computed for plc_queens(1,_432) -> 1 sols in 0.000088 seconds.
%% Computed for plc_queens(2,_432) -> 0 sols in 0.000066 seconds.
%% Computed for plc_queens(3,_432) -> 0 sols in 0.00008 seconds.
%% Computed for plc_queens(4,_432) -> 2 sols in 0.000201 seconds.
%% Computed for plc_queens(5,_432) -> 10 sols in 0.000799 seconds.
%% Computed for plc_queens(6,_432) -> 4 sols in 0.002714 seconds.
%% Computed for plc_queens(7,_432) -> 40 sols in 0.0094 seconds.
%% Computed for plc_queens(8,_432) -> 92 sols in 0.033084 seconds.
%% Computed for plc_queens(9,_432) -> 352 sols in 0.155727 seconds.
%% Computed for plc_queens(10,_432) -> 724 sols in 0.761938 seconds.
%% Computed for plc_queens(11,_432) -> 2680 sols in 4.159389 seconds.
%% Computed for plc_queens(12,_149) -> 14200 sols in 25.130361 seconds.
%% Computed for plc_queens(13,_149) -> a

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Equations over Finite Trees
%% Check that two trees are isomorphic (same elements in each level)

iso(Tree, Tree). 
iso(t(R, I1, D1), t(R, I2, D2)) :- 
    iso(I1, D2), 
    iso(D1, I2). 

 %% ?- iso(t(a, b, t(X, Y, Z)), t(a, t(u, v, W), L)).

 %% ?- iso(t(a, t(b, c, d), t(e, f, g)), T).
 %% T = t(a,t(b,c,d),t(e,f,g)) ? ;
 %% T = t(a,t(e,f,g),t(b,c,d)) ? ;
 %% T = t(a,t(e,g,f),t(b,c,d)) ? ;
 %% T = t(a,t(e,f,g),t(b,d,c)) ? ;
 %% T = t(a,t(e,g,f),t(b,d,c)) ? ;


