5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Note that this is always possible with four colors or less (as long as all countries are contiguous). $\endgroup$ – Doorknob May 15 '14 at 3:34
  • $\begingroup$ Yes I agree with Doorknob. The problem you mentioned is the map colouring problem, you can easily find these algorithms over internet. The minimum number of colours required to colour a map will be 4 or less. here is the Wikipedia link for the four colour algorithm for colouring map en.wikipedia.org/wiki/Four_color_theorem $\endgroup$ – Strikers May 15 '14 at 6:21
  • 1
    $\begingroup$ Can you point to a more precise definition of the rules? (The name “mpire” is proving hard to google.) Are the empires contiguous or not? Are they on a planar map? Is the map bounded? Do point intersections count or only lines? $\endgroup$ – Gilles May 21 '14 at 19:01
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In some cases it is possible to use 1,2 or 3 colour maybe you need mentioned that in your answer :) $\endgroup$ – martijnn2008 May 22 '14 at 13:09
  • $\begingroup$ As soon as you have at least one 'empire' that is: 1) surrounded entirely by others, 2) has more then two neighbours, 3) has an odd number of neighbours, you will need the 4 colors.. one for the center, and you don't have enough with 2 colors to alternate the neighbours. I can imagine that happening alot. $\endgroup$ – Tim Couwelier Oct 6 '14 at 10:00
  • 1
    $\begingroup$ Sidenote for fun: gamedesign.jp/flash/fourcolor/fourcolor.html is an interesting twist - player and computer take turns in coloring in a region, you need to force computer to fail. $\endgroup$ – Tim Couwelier Oct 6 '14 at 10:06
  • $\begingroup$ This answer is an algorithm not a (gaming)-strategy. It assumes all playets work together. I don't know MPire but I assume some gaming-rules come in.. The goal might not be a fully solved map... $\endgroup$ – BmyGuest Jan 7 '15 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.