:- module(_,_).
:- use_package(clpfd).

:- use_module(library(aggregates),[findall/3]).
:- use_module(library(lists),[length/2]).
:- use_module(library(format)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Some first queries: 

% X #= A + B, A in 1..3, B in  3..7.
% X #= A - B, A in 1..3, B in 3..7.
% X #= A - B, A in 1..3, B in 3..7, X #>= 0.
% domain([X, Y, Z],1,1000), X*X+Y*Y #= Z*Z, X #>= Y, labeling([],[X,Y,Z]).


% --- This is for fd X #= A - B, A in 1..3, B in 3..7, fd_min(X, X). # <- No fd_min?
% --- domain([X, Y, Z],1,1000), X*X+Y*Y #= Z*Z, X #>= Y, minimize(labeling([],[X,Y,Z]),X).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% smm([S,E,N,D,M,O,R,Y])
   
smm_no_labeling(Vars) :-
    Vars = [S,E,N,D,M,O,R,Y], 
    domain(Vars, 0, 9),
    0 #< S, 0 #< M,
    all_different(Vars),
              S*1000 + E*100 + N*10 + D +
              M*1000 + O*100 + R*10 + E #=
    M*10000 + O*1000 + N*100 + E*10 + Y.

smm(Vars) :-
    Vars = [S,E,N,D,M,O,R,Y], 
    domain(Vars, 0, 9),
    0 #< S, 0 #< M,
    all_different(Vars),
    S*1000 + E*100 + N*10 + D +
    M*1000 + O*100 + R*10 + E #=
    M*10000 + O*1000 + N*100 + E*10 + Y,
    labeling([], Vars),
    pp_smm(Vars).

pp_smm([S,E,N,D,M,O,R,Y]) :-
    format("~n   ~w ~w ~w ~w~n",  [S,E,N,D]),
    format(  " + ~w ~w ~w ~w~n",  [M,O,R,E]),
    format(  " ---------~n",             []),
    format( " ~w ~w ~w ~w ~w~n",[M,O,N,E,Y]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Project management problem

pn1(A,B,C,D,E,F,G) :- 
   domain([A,B,C,D,E,F,G], 0, 10), 
    A #>= 0, G #=< 10, 
    B #>= A, C #>= A, D #>= A, 
    E #>= B + 1, E #>= C + 2, 
    F #>= C + 2, F #>= D + 3, 
    G #>= E + 4, G #>= F + 1.

% 
% Queries:
% use_package(clpfd).
% pn1(A,B,C,D,E,F,G).
% minimize(pn1(A,B,C,D,E,F,G),G).
% Alt:          pn1(A,B,C,D,E,F,G), minimize(true,G).
% Alt (for fd): pn1(A,B,C,D,E,F,G), fd_min(G, G).

pn2(A, B, C, D, E, F, G, X) :- 
    domain([A,B,C,D,E,F,G,X], 0, 10),
    A #>= 0, G #=< 10, 
    B #>= A, C #>= A, D #>= A, 
    E #>= B + 1, E #>= C + 2, 
    F #>= C + 2, F #>= D + 3, 
    G #>= E + 4, G #>= F + X.

% Queries:
% pn2(A, B, C, D, E, F, G, X).
% minimize(pn2(A,B,C,D,E,F,G,X), G), maximize(true,X).
% (for fd) pn2(A, B, C, D, E, F, G, X), fd_min(G, G), fd_max(X, X).

pn3(A,B,C,D,E,F,G,X,Y) :- 
    domain([A,B,C,D,E,F,G,X,Y], 0, 10),
    A #>= 0, G #=< 10, 
    X #>= 2, Y #>= 2, X + Y #= 6, 
    B #>= A, C #>= A, D #>= A, 
    E #>= B + X, E #>= C + 2, 
    F #>= C + 2, F #>= D + Y, 
    G #>= E + 4, G #>= F + 1.

% Queries:
% minimize(pn3(A,B,C,D,E,F,G,X,Y), G). (Worked badly in SICStus?)
% (for fd) pn3(A,B,C,D,E,F,G,X,Y), fd_min(G, G).
% pn3(A,B,C,D,E,F,G,X,Y), minimize(labeling([],[A,B,C,D,E,F,G,X,Y]),G).

queens(N, Qs, Type) :-
        constrain_values(N, N, Qs),
        all_different(Qs),  % built-in constraint
        labeling(Type,Qs).

constrain_values(0, _N, []).
constrain_values(N, Range, [X|Xs]) :-
        N > 0, N1 is N - 1, X in 1 .. Range,
        constrain_values(N1, Range, Xs), no_attack(Xs, X, 1).

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

% Queries:
%% Very good at finding one solution!
% queens(20, Q, [ff]).
% queens(100, Q, [ff]). (!)
% 
%% Not so much difference for all solutions!
% plall(11, Q).
% plall(12, Q).
% plall(13, Q).
% clpall(11, Q).
% clpall(12, Q).
% clpall(13, Q).

%% ?- between(1,100,N),clock(queens(N,L,[ff])), fail.
%% Computed queens(35,_149,[ff]) in 0.06397699999999999 seconds.
%% Computed queens(79,_149,[ff]) in 0.28325799999999995 seconds.
%% Computed queens(80,_149,[ff]) in 0.207631 seconds.

%% ?- between(1,100,N),clock_all(queens(N,L,[ff])), fail.
%% Computed for queens(1,_1418,[ff]) -> 1 sols in 0.00021799999999999999 seconds.
%% Computed for queens(2,_1418,[ff]) -> 0 sols in 0.000272 seconds.
%% Computed for queens(3,_1418,[ff]) -> 0 sols in 0.000442 seconds.
%% Computed for queens(4,_1418,[ff]) -> 2 sols in 0.00091 seconds.
%% Computed for queens(5,_1418,[ff]) -> 10 sols in 0.003085 seconds.
%% Computed for queens(6,_1418,[ff]) -> 4 sols in 0.005988 seconds.
%% Computed for queens(7,_1418,[ff]) -> 40 sols in 0.018727 seconds.
%% Computed for queens(8,_1418,[ff]) -> 92 sols in 0.060753999999999996 seconds.
%% Computed for queens(9,_1418,[ff]) -> 352 sols in 0.255244 seconds.
%% Computed for queens(10,_1418,[ff]) -> 724 sols in 1.039173 seconds.
%% Computed for queens(11,_1418,[ff]) -> 2680 sols in 5.02972 seconds.
%% Computed for queens(12,_1418,[ff]) -> 14200 sols in 26.924507000000002 seconds.
%% Computed for queens(13,_158,[ff]) ->   C-c C-c

plall(N,L) :- findall(_X,plqueens(N,_X),_S), length(_S,L).
clpall(N,L) :- findall(_X,queens(N,_X,[ff]),_S), length(_S,L).

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).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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.

