300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa MelayuFloodfill©
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 Nk 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 4N.
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?
- It is useful to colour at first a region that has as many neighbours as possible because if that region gets colour A then all its neighbours will obtain a restriction not to get colour A. This reduces the number of colour choices for these neighbouring regions and thus reduces the number of later tries if colouring turns out to be hard.
Q. Which choice of colours is free?
- The colour used in the very first colouring is definitely free.
- The first time that a second colour is used to colour a region this choice of colour is free if this region touches a region with the first colour, i.e. if a second colour is necessary.
- The first time that a third colour is used to colour a region, this choice of colour is free if this region touches a region with the first colour and a region with the second colour, i.e. if a third colour is necessary.
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 4N (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 N1 and N2 regions (N = N1 + N2), needing now at most only 4N1 + 4N2 tries which is much less than 4N1 × 4N2 = 4N 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.
Follow or subscribe for updates: