The MPire coloring game is a game where several "empires" are laid out touching each other. Your task is to color each empire a different color, and not let two of the same color touch. You also have to use as few colors as possible.
I was wondering if anyone had specific strategies for this game? Is it better to start in the center or a corner? Plan a strategy around trick points in the map?
As others have mentioned in the comments, this is covered by a well-known mathematical theorem called The Four Colour Theorem. Any map can be coloured as you describe using only four colours. The actual algorithm, though, sounds rather complex.
This answer on Stack Overflow gives an easier algorithm that will use at most five colours.
The four-color mapping algorithm is very complex, with 1476 special cases that you have to handle in your code. If you can spare one more color, the five color mapping algorithm will meet your requirements, is much simpler, and there is a nice write up on it at devx.com.
As a brief summary of the algorithm, the strategy is to find a region whose colour would be obvious if the rest of the map were already coloured. Then "remove" that region from the map and repeat the process until the map is empty. If you kept track of the order you removed the regions, you can now add them back in the reverse order, choosing colours as you do so.
To see the two rules for choosing a region to remove, see the detailed write up.
