# Four Colour Problem

Main references on the Internet are: 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

## 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.