%Versione SWI-Prolog

coloring(Regions,Map,NoOfColors,Ass) :-
     assign(Regions,Colors,Ass), 
     Colors in 1..NoOfColors,
     valid(Map,Ass),
     label(Colors).      % labeling([],Colors). %per SICStus Prolog


assign([],[],[]).
assign([R|Regions],[C|Colors],[[R,C]|Ass]) :-
     assign(Regions,Colors,Ass).

valid([],_).
valid([[R1,R2]|Map],Ass) :-
     member([R1,C1],Ass),
     member([R2,C2],Ass), 
     C1 #\= C2,
     valid(Map,Ass).
     
member(X,[X|_R]).
member(X,[_Y|R]) :-
     member(X,R).

% Sample goals
%
% ?- coloring([r1,r2,r3],[[r1,r2],[r2,r3]],2,Ass).
%
% ?- coloring([r1,r2,r3,r4,r5,r6,r7,r8,r9,r10,r11,r12],
%              [[r1,r2],[r2,r3],[r3,r4],[r4,r5],[r5,r6],[r6,r7],[r7,r8],[r8,r9],[r9,r10],[r10,r11],[r11,r12]],
%              4,
%              Ass).

regions(1,[r1,r2,r3]).
regions(2,[italy,austria,swiss,france,slovenia]).
regions(3,[r1,r2,r3,r4,r5,r6,r7,r8,r9,r10,r11,r12]).
%regions(3,[r1,r2,r3,r4,r5,r6,r7,r8,r9,r10]).

map(1,[[r1,r2],[r2,r3]]).
map(2,[[italy,austria],[italy,france],[italy,slovenia],
       [italy,swiss],[austria,swiss],
       [austria,slovenia],[france,swiss]]).
map(3,[[r1,r2],[r2,r3],[r3,r4],[r4,r5],[r5,r6],[r6,r7],[r7,r8],[r8,r9],[r9,r10],
      [r10,r11],[r11,r12]]).
%map(3,[[r1,r2],[r2,r3],[r3,r4],[r4,r5],[r5,r6],[r6,r7],[r7,r8],[r8,r9],[r9,r10]]).

sample_coloring(N,Ass,K) :-
       regions(N,R), 
       map(N,M),
       coloring(R,M,K,Ass).

% Sample goal
%
% ?- use_module(library('clp/bounds')).
% ?- sample_coloring(2,Ass,4).
