8/10/12



microsiervos

Flood Fill: el Teorema de los cuatro colores, llevado a la práctica

Cualquier mapa geográfico puede ser coloreado con cuatro colores diferentes, de forma que no haya regiones adyacentes con el mismo color.

¡Cuidado que engancha!

Si quieres comprobar si el teorema de los cuatro colores es cierto, nada más fácil que jugar un rato a Flood Fill [Flash], un sencillo juego que está basado precisamente en esta idea. El juego comienza con unas pocas regiones que hay que colorear con el ratón y se va complicando poco a poco, pero siempre hay únicamente hay cuatro colores disponibles. Pese a que a veces parece casi imposible todos los mapas tienen solución. (Detalle importante: dos regiones que se toquen en un solo punto no se consideran conectadas).

Y es que aunque se intuía que el teorema era correcto en 1976 Kenneth Appel y Wolfgang Haken publicaron la demostración definitiva, con ayuda de un ordenador que examinó millones de mapas. El teorema era cierto y cuatro colores bastaban para colorear cualquier mapa según el planteamiento original.

Curiosamente, da igual que el mapa esté limitado a un cuadrado como en este juego o sobre una superficie cilíndrica (como la del Pac-Man, en la que se «tocan» dos laterales) o incluso que esté sobre la superficie de una esfera como un globo terráqueo. Tan solo cuando el mapa está dibujado enrevesadamente sobre una superficie toriodal la cosa se complica y son necesarios hasta 7 colores.