Four Colour Problem

Main references on the Internet are:

The four colour theorem
The Four Color Theorem

Instead of re-iterating the theoretical work on this subject, I have succeeded in devising a rather general computer program, which attempts to do Four Colouring on Bit MaPs (BMP files) in practice.
The final algorithm is optimal, in the sense that it uses the minimum number of colors. Most of the time 4 of them are required (according to the Four Color Theorem); see below at 'Best Results so far'. But there are several other goodies in the program as well (and I find them equally important at least):

An algorithm which generates closed and oriented Contour lines, for quite arbitrary Black and White Bitmaps
An algorithm for classifying all of the Countries, especially those with Enclaves inside (also with a robust definition of the "inside" notion)
Determining the Neighbours of a Country, treated like solving a Radiative Heat Transfer problem in 2-D, where white pixels are the "opaque" medium
Euclid's GCD (Greatest Common Divisor) Algorithm, for obtaining a discrete approximation to straight lines-of-sight through the B/W medium

Executables

Best practice: only download the latest version
Don't forget to download some BitMaPs as well

Disclaimer: anything FREE comes without guarantee!
But, in the latter case, please drop some notification at the author's Email adress.

Country Maps

(*) Nederlandse Informatica Olympiade 1999 opgave 3

BMP images used

[ 1 ] , [ 2 ] , [ 3 ] , [ 4 ] , [ 5 ] , [ 6 ] , [ 7 ] , [ 8 ] , [ 9 ] , [ 10 ] , [ 11 ] , [ 12 ] , [ 13 ] , [ 14 ] , [ 15 ] , [ 16 ] , [ 17 ] , [ 18 ] , [ 19 ] .

Best Results so far

Country Map	# colours
Afrika.bmp	4
Boxville.bmp	4
Bump.bmp	3
col0.bmp	2
Islands.bmp	2
Popdale.bmp	4
Swirl.bmp	2
map_tyler.bmp	4
map_tara.bmp	4
map_miker.bmp	4
map_mike.bmp	4
map_jummy.bmp	4
map_eric.bmp	4
map_amanda2.bmp	4
map_amanda1.bmp	4
nio1.bmp	4
nio2.bmp	4
Wheel1.bmp	4
Wheel2.bmp	3


Country Map   # Colorings  Calculations
-------------------------------------------
Afrika.bmp   =  1.572.480  / (4!)^2 = 2.730
Boxville.bmp =  2.998.080  / (4!)^2 = 5.205
Bump.bmp     =         36  (see details)
Col0.bmp     =          2
Islands.bmp  =          2  (same details)
Map_Eric.bmp =        144  (same details)
Map_Mike.bmp =     62.208  / (4!)^2 = 108
Map_Tara.bmp > 34.400.000  (combinatorial explosion)
Popdale.bmp  > 22.500.000  (combinatorial explosion)
Swirl.bmp    =          2
nio1.bmp     =     49.152  / (4!) = 2048 = 2^11
nio2.bmp     =        480  / (4!) = 20
Wheel1.bmp   =      8.184  / (4!) = 341
Wheel2.bmp   =          6  (same details)

Additional maps from a 'sci.math' poster :
blueprint (not found) & coloured ; blueprint (not found) & coloured ; blueprint & coloured ; blueprint & coloured ; blueprint & coloured ; blueprint & coloured , also found here.