Prolog Program 4: Map Coloring

• A Map Coloring Problem
  • 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]).
    
    
    

• Template program for colors.pl

  | ?- paint('West Europe', X).
  X = [germany:red,france:red,austria:red,italy:red,switzerld:red,luxembrg:red,
  holland:red,belgium:red,spain:red,portugal:red] ? 
  
  X = [germany:green,france:red,austria:red,italy:red,switzerld:red,luxembrg:red,
  holland:red,belgium:red,spain:red,portugal:red] ? 
  
  X = [germany:blue,france:red,austria:red,italy:red,switzerld:red,luxembrg:red,
  holland:red,belgium:red,spain:red,portugal:red] ?
  
  etc.
  

• This "solution" needs help. It is generating maps of colors for each country, but the adjacent countries have the same color (not allowed in the problem).
  Fix this template program to generate map solution(s) where adjacent countries do not share the same color.

• Getting in to this code:
  • To generate possible colors from the color list:

    If the first parameter in member(X,List) is left as a variable - you know the List, 
    but not the X - this will generate the members of the list individually:
    
    	colors([red,green,blue,purple]).
    
    	getcolor(X) :- colors(List), member(X,List).
    	/*
    	| ?- getcolor(X).    
    	X = red ? ;
    	X = green ? ;
    	X = blue ? ;
    	X = purple ? ;
    	*/
    

  • Finding the neighbors of a given country from a given map:

    	findneighbors(X, Map, Who) :-
    		map(Map, Countries),
    		neighbors(X,Countries,Who).
    
    	/*
    	|?- findneighbors(holland,'West Europe',X).
    	X = [belgium,germany]
    	*/
    

  • Determining if two countries on a given map are adjacent:

    	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 tools you may need to 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).
    

• Prolog