/* 			Map Coloring

It's known that only 4 colors are needed to paint any map so that no two
neighboring states have the same color.  

Write a Prolog program that receives a map and a list of 4 colors and 
produces a colored map.

The map is represented by a list of states, each of which is a state name and
a list of neighboring states.

For example, the maps of Australia and Western Europe are represented by the
following maps.

*/


map('Australia',
	[wa: [nt,sa], nt: [wa,sa,qld], qld:[nt,sa,nsw],
	nsw: [qld,sa,vic], vic: [sa,nsw], tas:[], 
	sa: [wa,nt,qld,nsw,vic]]).

map('West Europe',
	[portugal: [spain],
	 spain: [portugal, france],
	 belgium: [france, holland, luxembrg, germany],
	 holland: [belgium, germany],
	 luxembrg: [france, belgium, germany],
	 switzerld: [france,germany,austria, italy],
	 italy: [france,switzerld, austria],
	 austria: [germany, switzerld, italy],
	 france: [spain,belgium,luxembrg, germany,switzerld, italy],
	 germany:[holland,belgium,luxembrg,france,switzerld, austria]]).

colors([red,green,blue,purple]).

getcolor(X) :- colors(List), member(X,List).
/*
| ?- getcolor(X).    
X = red ? ;
X = green ? ;
X = blue ? ;
X = purple ? ;
*/

%Use the "write" statements for tracing

paint(Map,ColoredMap) :-
	map(Map, Countries),
	colors(ColorList),
	arrangecolors(Countries,ColorList,[], ColoredMap).
%Add this for tracing:
%	write('ColoredMap is '), write(ColoredMap), nl.   


arrangecolors([],_,ColoredMap,ColoredMap).
%Use for tracing:
%     :- write('Colormap='),
%	write(ColoredMap),nl.
arrangecolors([Country:Neighbors|Rest], ColorList, TempList, ColoredMap) :-
	member(Color,ColorList),
%write('Color:'), write(Color),write(' TempList:'), write(TempList),nl,
	arrangecolors(Rest,ColorList,[Country:Color|TempList], ColoredMap).


findneighbors(X, Map, Who) :-
	map(Map, Countries),
	neighbors(X,Countries,Who).

neighbors(X,[],[]).
neighbors(X,[X:Neighbors|_], Neighbors) :- !.  % Try this without the !
neighbors(X,[_|RestofCountries], Neighbors) :-
	neighbors(X,RestofCountries, Neighbors).

/*
|?- findneighbors(holland,'West Europe',X).

X = [belgium,germany]

yes
*/

%adjacent(X,Y,Map).

adjacent(X,Y,Map) :-
	findneighbors(X, Map, Countries),
	member(Y, Countries).

/*
| ?- adjacent(holland, germany, 'West Europe').
true ? 
| ?- adjacent(holland, france, 'West Europe').
no
| ?- adjacent(spain, france, 'West Europe').  
true ? 
*/


% Other tool procedures that you may use:

different(C, Nbs, [S1:C1|Rest]) :-
	not((member(S1,Nbs), C = C1)),
	different(C, Nbs,Rest).
different(_,_,[]).

member(X, List) :- List = [H|T], X = H.
member(X, List) :- List = [_|T], member(X,T).

not(G) :- G, !, fail.
not(G).