%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                           %
% Basic Constraints Solvers %
%                           %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- module(constraints, [gat/1, backtrack/1, nodeConsist/1, nodeConsistFF/1]).


% Generate and Test (GAT)
gat(Assign) :-
    vars(Vars),
    generate(Vars, Assign),
    test(Assign).


generate([], []).
generate([X:DX | Vars], [(X,V) | Assign]) :-
    member(V, DX),
    generate(Vars, Assign).


test([]).
test([(X,V) | L]) :-
    test((X,V), L),
    test(L).

test(_, []).
test((X1,V1), [(X2,V2) | L]) :-
    consistent((X1,V1), (X2,V2)),
    test((X1,V1), L).






% Simple backtrack
backtrack(Assign) :-
    vars(Vars),
    backtrack(Vars, [], Assign).

backtrack([], _, []).
backtrack([X:DX | Vars], PartialAssign, [(X,V) | Assign]) :-
    member(V, DX),
    test((X,V), PartialAssign),
    backtrack(Vars, [(X,V) | PartialAssign], Assign).







% Node consistency
nodeConsist(Assign) :-
    vars(Vars),
    nodeConsist(Vars, [], Assign).

nodeConsist([], _, []).
nodeConsist([X:DX | Vars], PartialAssign, [(X,V) | Assign]) :-
    member(V, DX),
    filtering(X, V, Vars, FilteredVars),
    nodeConsist(FilteredVars, [(X,V) | PartialAssign], Assign).

filtering(_, _, [], []).
filtering(X1, V1, [X2:D2 | Vars], [X2:FilteredD2 | FilteredVars]) :-
    bagof(V2, (member(V2, D2), consistent((X1,V1), (X2,V2))), FilteredD2),
    filtering(X1, V1, Vars, FilteredVars).






% Node consistency with first fail
nodeConsistFF(Assign) :-
    vars(Vars),
    nodeConsistFF(Vars, [], AssignUnsorted),
    msort(AssignUnsorted, Assign).


nodeConsistFF([], Assign, Assign).
nodeConsistFF(Vars, PartialAssign, Assign) :-
    minDomain(Vars, X:DX, VarsWhitoutX),
    member(V, DX),
    filtering(X, V, VarsWhitoutX, FilteredVars),
    nodeConsistFF(FilteredVars, [(X,V) | PartialAssign], Assign).

minDomain([X:DX | Vars], Xmin:DXmin, VarsWhitoutXmin) :-
    length(DX, N),
    minDomain(Vars, X:DX, N, Xmin:DXmin, VarsWhitoutXmin).

minDomain([], X:DX, _, X:DX, []).
minDomain([X:DX | Vars], Y:DY, N, Z:DZ, [Y:DY | VarsWhitoutZ]) :-
    length(DX, M),
    M < N, !,
    minDomain(Vars, X:DX, M, Z:DZ, VarsWhitoutZ).
minDomain([X:DX | Vars], Y:DY, N, Z:DZ, [X:DX | VarsWhitoutZ]) :-
    minDomain(Vars, Y:DY, N, Z:DZ, VarsWhitoutZ).