% File: ECMI01.AI2_COLOURMAP
% Author: Leon Sterling
% Updated: 17 November 83
% Purpose: simple depth first search of a set of possibilities
% Needs: UTIL for member/2

% The top level is test/0.
%
% This procedure colours a map so that no two adjoining countries have
% the same colour. It is a famous theorem in mathematics, recently
% proved, that four colours are enough. It is illustrated with the
% map of Europe.
%   The program works by taking each country in turn and trying to put
% it on the map. It checks the country's neighbours to see which of
% the colours can still be used. It stops when all the countries have
% been coloured. With 4 colours and 10 countries there are at most
% 1,048,576 combinations to try!
%   assign_colours(CountriesToDo, MapSoFar, Answer) is intended to have
% as its first argument a list of the countries not yet dealt with, and
% as its second argument a list of the countries coloured so far, together
% with their colours, in the form [ ..., Country=Colour, ...]. The third
% argument is intended to be a variable, which gets instantiated to the
% answer at the very end.

assign_colours([], Map, Map) :-
	!.
assign_colours([Country|ToBeColoured], MapSoFar, Map) :-
	colours(Colours),
	exclude(MapSoFar, Country, Colours, Permitted),
	member(Colour, Permitted),
	assign_colours(ToBeColoured, [Country=Colour|MapSoFar], Map).

% To find out which colours are permitted for the current country, we
% have to check the countries which have been coloured so far, and
% cross off the colours assigned to the neighbours of this country.

exclude([Neighbour=Colour|Map], Country, Colours, Permitted) :-
	neighbour(Neighbour, Country),
	!,
	del(Colour, Colours, Remaining),
	exclude(Map, Country, Remaining, Permitted).
exclude([Other=_|Map], Country, Colours, Permitted) :-
	% Other is not a neighbour of Country
	!,
	exclude(Map, Country, Colours, Permitted).
exclude([], _, Permitted, Permitted).

del(Element, [Element|Rest], Rest).
del(Element, [X|Rest], [X|RestOfAns]) :-
	del(Element, Rest, RestOfAns).

% To save writing everything twice, we write just one clause
% per border, and look it up both ways.

neighbour(CountryA, CountryB) :-
	contact(CountryA, CountryB).
neighbour(CountryA, CountryB) :-
	contact(CountryB, CountryA).

% The geographic data:

contact(france, spain).			contact(spain, portugal).
contact(france, italy).
contact(france, switzerland).		contact(italy, austria).
contact(france, belgium).		contact(italy, switzerland).
contact(france, west_germany).
contact(france, luxembourg).		contact(austria, switzerland).
					contact(austria, west_germany).
contact(belgium, holland).		contact(switzerland, west_germany).
contact(belgium, luxembourg).		contact(holland, west_germany).
contact(belgium, west_germany).		contact(luxembourg, west_germany).

countries([france, west_germany, portugal, spain, belgium, 
	   holland, luxembourg, italy, switzerland, austria]).

colours([red, white, green, yellow]).

test :-     
	countries(ToBeColoured),
	assign_colours(ToBeColoured, [], Map),
	write('Europe can be coloured this way:'), nl,
	write(Map),  nl.