%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%    Map coloring    %%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%   Last revision: July 2005 (G.Rossi)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% The problem.
% Given a map of n regions r_1,...,r_n, and a set
% {c_1,...,c_m} of colors,
% find an assignment of colors to the regions of the map 
% such that no two neighbouring regions have the same color.

% Data representation.
% A map is represented as an undirected graph <N,E> where 
% N is the set of nodes (the regions) and
% E is the set of edges (unordered pairs --i.e., sets-- of 
% neighbouring regions). 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Solution #1 - coloring/3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% The regions are represented by uninitialized variables.
% The arcs are sets consisting of two variable elements.
% An assignment of colors to regions is the collection of 
% bindings computed for the variables representing the regions.


coloring(Regions,Map,Colors) :-
     Regions = Colors &
     forall(R in Regions, {R} nin Map).


%%% Sample goals	  
%
% {log}=> coloring({R1,R2,R3},{{R1,R2},{R2,R3}},{c1,c2}).
% R1 = c1, R2 = c2, R3 = c1
% Another solution?  (y/n)y
% R1 = c2, R2 = c1, R3 = c2
% Another solution?  (y/n)y
% no
%
%%%
%
% With a partially specified set of colors
%
% {log}=> coloring({R1,R2,R3},{{R1,R2},{R2,R3}},{X,c2}).
% R1 = X, R2 = c2, R3 = X, X neq c2    (2 times)
% Another solution?  (y/n)y
% R1 = c2, R2 = X, R3 = c2, X neq c2   (2 times)
% Another solution?  (y/n)y
% no


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Solution #2 - coloring/4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% The regions are represented by constants.
% The arcs are sets consisting of two constants elements.
% An assignment of colors to regions is represented
% as a set of ordered pairs [r,c] where r is a region and c
% is the color assigned to it.


coloring(Regions,Map,Colors,Ass) :-
     assign(Regions,Colors,Ass) & 
     forall(P in Map,different(P,Ass))!.

assign({},_,{}).
assign(Reg,Colors,{[R,C]/Ass}) :-
     (Reg = {R/Regions} & R nin Regions)! &
     C in Colors &
     assign(Regions,Colors,Ass).

different({R1,R2},Ass) :-
     [R1,C1] in Ass & 
     [R2,C2] in Ass &
     C1 neq C2.


%%% Sample goals
%  
% {log}=> coloring({r1,r2,r3},{{r1,r2},{r2,r3}},{c1,c2},Ass).
% Ass = {[r1,c1],[r2,c2],[r3,c1]}
% Another solution?  (y/n)y
% Ass = {[r1,c2],[r2,c1],[r3,c2]}
% Another solution?  (y/n)y
% no
%
%%%
%
% With a partially specified set of colors
%
% {log}=> coloring({r1,r2,r3},{{r1,r2},{r2,r3}},{X,c2},Ass).
% Ass = {[r1,X],[r2,c2],[r3,X]}, X neq c2
% Another solution?  (y/n)y
% Ass = {[r1,c2],[r2,X],[r3,c2]}, X neq c2
% Another solution?  (y/n)y
% no


%%% Another (more realistic) example

% Auxiliary predicates 

sample_regions({italy,austria,swiss,france,slovenia}).
sample_map({{italy,austria},{italy,france},{italy,slovenia},
       {italy,swiss},{austria,swiss},
       {austria,slovenia},{france,swiss}}).
sample_colors({white,yellow,red,blue}).

sample_coloring(Ass) :-
       sample_regions(R) & sample_map(M) & sample_colors(C) & 
       coloring(R,M,C,Ass).

%%% Sample goal
%
% {log}=> sample_coloring(Ass).
% Ass = {[italy,white],[austria,yellow],[swiss,red],[france,yellow],[slovenia,red]}
% Another solution?  (y/n)y
% ...
% Ass = {[italy,white],[austria,yellow],[swiss,red],[france,yellow],[slovenia,blue]}
% Another solution?  (y/n)y
% ...
% Ass = {[italy,white],[austria,yellow],[swiss,red],[france,blue],[slovenia,red]}
% ...


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% start predicates
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

start :- 
   consult_lib &
   nl &
   write('Coloring of a map') & nl & nl &
   write('Give the goal coloring(Regions,Map,Colors): ') & nl &
   write('where Regions is a set of unintialized variables representing regions') & nl &
   write('Map is a set of sets {R1,R2} representing neighbouring regions') & nl &
   write('Colors is the set of colors.') & nl & 
   write('                       or                   ') & nl &
   write('Give the goal coloring(Regions,Map,Colors,Assignments): ') & nl &
   write('where Regions is a set of constants representing regions') & nl &
   write('Map is a set of sets {r1,r2} representing neighbouring regions') & nl &
   write('Colors is the set of colors') & nl &
   write('Assignments is a set of ordered pairs [r,c] where r is a region ') & nl &
   write('and c is the color assigned to it.') & nl & start2.
start2 :- 
   nl &
   write('Sample goals.               ') & nl &
   write('Give the goal sample_regions(Regions): to get a sample set of regions') & nl &
   write('give the goal sample_map(Map): to get the related map') & nl &
   write('give the goal sample_colors(Colors): to get a sample set of colors.') & nl &
   write('Give the goal sample_coloring(A): ') & nl &
   write('to get an admissible coloring for the sample map.') & nl & nl.

%:-start.