%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%    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). 
% Regions and colors are represented by constants.
% 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
%
%%%
%
% Same goal as above but using integers to represent colors:
% executed much more efficiently thanks to the (automatic) use 
% of the FD solver.
%
% {log}=> coloring({r1,r2,r3},{{r1,r2},{r2,r3}},int(1,2),Ass).
% Ass = {[r1,1],[r2,2],[r3,1]}
% Another solution?  (y/n)y
% Ass = {[r1,2],[r2,1],[r3,2]}
% 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