Map Colouring – Prolog

%Map Colouring %
%Directed Studies – Assignment 2 %
%By: Nicholas Webb. %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Question 1: adjacency relation among the states.
%
state_list([[qld,nsw],[qld,nt],[qld,sa],[nsw,act],[nsw,vic],[nsw,sa],
[vic,sa],[sa,nt],[sa,wa],[nt,wa]]).

adjacent(S1,S2) :- state_list(L), member([S1,S2],L);
state_list(L), member([S2,S1],L).

%Question 2&3: if given a list of states will return a valid colouring
%using the naive approach of generating a colouring for an entire list
%of states. It also has the following functionality:given a colouring
%(Colouring) that could be a valid colouring, it produces the
%corresponding list of states (States) whose colouring it might be.
%
colour_list([red, yellow, blue, green]).

valid_colouring(States,Colouring) :-
colour_list(Colours), colour_all(States,Colours,Colouring),
\+ conflict(Colouring).

colour_all([],_,[]).
colour_all([State|States],Colours,[[State,Colour]|T]) :-
member(Colour,Colours),
colour_all(States,Colours,T).

conflict(Colouring) :-
member([State1,Colour],Colouring),
member([State2,Colour],Colouring),
adjacent(State1,State2).

%Question 4: smarter map colouring program that is more efficient
%than the naive approach. Here a state is only coloured with a
%colour if it can be shown that none of its neighbors have the colour.
%
smart_colouring(States,Colouring) :-
colour_list(Colours), colour_correct([],States,Colours,Colouring).

colour_correct(_,[],_,[]).
colour_correct(Sofar,[State|States],Colours,[[State,Colour]|Colouring]) :-
member(Colour,Colours),
\+ dontColour(State,Colour,Sofar),
colour_correct([[State,Colour]|Sofar],States,Colours,Colouring).

dontColour(State,Colour,Colouring) :-
adjacent(State, Neighbor),
member([Neighbor,Colour],Colouring).