Map Colouring

% A map colouring program (after Bratko, ``Prolog Programming for AI'' p190)

% THE PROBLEM : To find a way of colouring a map using only 4 colours in
%               such a way that no pair of neighbouring countries are
%               the same colour.
%**********************************************************************

% Predicate : colour_countries(-List).
% Returns a List of terms of the form:
%       Country/Colour where - Country is the name of some country.
%                            - Colour is the map colour for that country.
% This program gives the following behaviour:
%
% | ?- colour_countries(X).
%
%     X=[austria/red,belgium/green,denmark/blue,france/red,
%       italy/yellow,netherlands/blue,portugal/blue,
%       spain/yellow,switzerland/blue,w_germany/yellow] 
%yes

% colour_countries/1 works by first using setof/3 to construct a list of terms
% of the form : Country/Var where - Country is the name of a country
%                                   Var is a variable
% It then uses colours/2 to bind each Var in this list to an appropriate colour

colour_countries(Colours):-
        setof(Country/_, X^ngb(Country,X), Colours),
        colours(Colours).

% Predicate : colours(+List)
% Succeeds when, given a List of elements of form Country/Colour, a value
% for each Colour can be found such that the Country to which it is attached
% has no neighbour of the same colour.

        % If there are no elements left in the list then just succeed.
colours([]).
        % For a list with head Country/Colour and tail Rest, colour all
        % the Rest then select a value for Colour from the list of candidates
        % then check that there is no country in Rest which neighbours
        % the Country just coloured and has the same Colour.,
colours([Country/Colour|Rest]):-
        colours(Rest),
        member(Colour, [yellow,blue,red,green]),
        \+ (member(Country1/Colour, Rest), neighbour(Country, Country1)).


% Predicate : neighbour(Country, Neighbour)
% Succeeds if Neighbour is a neighbour of Country

neighbour(Country, Country1):-
        ngb(Country, Neighbours),
        member(Country1, Neighbours).


% Predicate : ngb(Country, Neighbours).
% Determines the list of Neighbours of a Country.

ngb(portugal, [spain]).
ngb(spain, [portugal,france]).
ngb(france, [spain,belgium,switzerland,w_germany,italy]).
ngb(belgium, [france,w_germany,netherlands]).
ngb(netherlands, [belgium,w_germany]).
ngb(w_germany, [netherlands,belgium,france,switzerland,austria,denmark]).
ngb(switzerland, [france,w_germany,austria,italy]).
ngb(austria, [w_germany,switzerland,italy]).
ngb(italy, [france,switzerland,austria]).
ngb(denmark, [w_germany]).


% Predicate : member(Element, List)
% Standard membership utility

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