%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%% 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 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