Floodfill ©

300000

Floodfill^©

Gesamtzahl der Spiele: 427326
Gesamtzahl der Siege: 209822

A Guide for Playing Floodfill

The problem of using a minimal number of colours to colour a map has a long history as explained, for example, in this Wikipedia article. The theorem that 4 colours are always enough to colour a plane map became famous as the first big mathematical theorem that could be proven only by computer and not through a human produced "mathematical" proof.

There is no algorithm known that always colours maps efficiently. With "efficiently" we mean that if the number of regions N is very large then the number of necessary colouring attempts grows only like N^k where k is a number that does not depend on N. In other words, for "efficient" algorithms the number of attempts grows only like a polynomial of N. Instead, known colouring algorithms have a so-called exponential complexity, i.e. the number of tries depends on N like 4^N.

If one were allowed to use 5 or 6 colours, or if the map needs only 2 colours, then efficient algorithms are known.

Another opportunity to get an efficient method is to drop the requirement that the algorithm is ALWAYS efficient. Such a heuristic (i.e. a set of instructions) that works at least in many cases is to be discussed below:

Q. Which region should be colored first?

Q. Which choice of colours is free?

Q. Which region should be coloured next?

We should colour a region next for which there is only one possible colour left so that we can not make a mistake in this colouring.
The number of colouring attempts is definitely less than 4^N (trying all 4 colours for all N regions). So this number of colouring attempts depends critically on the number of regions N. Consequently it is useful if a colouring splits the white (uncoloured) part of the map into separate disconnected white sub-maps which then can be coloured on their own. These regions have only N₁ and N₂ regions (N = N₁ + N₂), needing now at most only 4^N₁ + 4^N₂ tries which is much less than 4^N₁ × 4^N₂ = 4^N tries.
If one wants to find the smallest number of colours that can colour a given map then one first has to check whether 2 colours are enough. This can be done efficiently.

If only two colours A and B are to be used and one of the regions already has a colour, then going around the point of intersection fixes the colour of all other regions:

This rule is also useful for a first colouring attempt of maps that need 3 or 4 colours. For example, if region 1 below has already colour A then regions 2 and 4 need a different colour and we have no idea what that could be but we know that colouring region 3 with colour A does not pose extra conditions on the colouring of regions 2 and 4, because they already have a neighbour of colour A.

Figure 3 shows only a small part of the map but the above heuristic can be made more precise for any map. If all neighbours of region 3 (in Figure 3, regions 2 and 4) have at least one neighbour of colour A (in Figure 3, region 1), then colouring region 3 with colour A can not be a mistake. The reason is that colouring region 3 with A does not create any new restriction on its neighbours because they are already forbidden to have colour A. So if in the further colouring process it turns out that a mistake has been made (because the number of colours is not enough), then there is no point in giving region 3 a different colour than A, some other colouring must be re-tried.
What if region 3 above is also a diagonal neighbour to another region, say region 9, which already has a different colour, like colour B? Should 3 be coloured with A or B? Also here it helps to check all neighbours of 3 whether they are already forbidden to have colour A or forbidden to have colour B. If neither is the case then we might wait with colouring 3.

Floodfill©

A Guide for Playing Floodfill

Floodfill^©