Color the map — France · 3 colours vs Ordenador
Color the map es un juego de dos jugadores sobre un mapa. Por turnos, cada jugador pinta una región vacía con uno de los colores de la paleta.
Única regla: dos regiones vecinas (que comparten frontera) no pueden tener el mismo color.
Pierde el jugador que se queda sin jugadas legales: o porque ya no quedan regiones vacías, o porque cada región libre tiene todos sus colores prohibidos por sus vecinos.
Niveles: France · 3 colours (Francia, 12 regiones, 3 colores — ¡al límite!) · Made-up country · 4 colours (país inventado con muchas vecindades, 4 colores) · Africa · 4 colours (mapa político simplificado, 4 colores).
Curiosidad: por el Teorema de los Cuatro Colores (1976), cualquier mapa real se puede colorear con 4 colores sin que dos vecinos compartan color.
El juego en una frase. "Colorea el mapa" es la versión juego de adversarios del problema clásico de coloreado de grafos: dos jugadores construyen, juntos pero compitiendo, un coloreado propio del grafo de adyacencia hasta que uno se queda sin jugadas legales.
Mapa = grafo planar. Cada región es un vértice; cada frontera compartida es una arista. Como los mapas terrestres son planos (sin cruces), siempre se obtiene un grafo planar. Esta es la conexión que hace el juego matemáticamente rico.
Teorema de los Cuatro Colores (Appel–Haken, 1976). Todo grafo planar es 4-coloreable: basta con 4 colores para colorear cualquier mapa sin que dos vecinos compartan color. Fue el primer teorema famoso demostrado con ayuda de ordenador. Por eso, niveles 2 y 3 (con 4 colores) siempre tienen solución posible — la cuestión es quién se queda sin jugadas antes.
Número cromático χ(G). El mínimo de colores necesarios para colorear un grafo. Para grafos planares χ ≤ 4 (4CT). Para Francia con 12 regiones, χ es típicamente 4 — y por eso el nivel 1 (sólo 3 colores) es especialmente brutal: hay configuraciones donde no se puede terminar, lo que significa que la partida acabará obligatoriamente con alguien sin jugadas. Buen tema de discusión: ¿es justo? ¿quién tiene ventaja?
Heurísticas humanas observables:
• Greedy — pintar la región con más vecinos primero (alto grado).
• Defensiva — pintar regiones aisladas con colores "raros" para reservar los frecuentes a zonas conflictivas.
• Trampa — forzar al rival a regiones donde solo le queda un color, y luego bloquearle ese color desde fuera.
Estrategia del juego perdedor (misère). Como pierde el primero sin jugadas, no se busca "rendimiento" sino paridad: dejar al rival con un número impar/par de movimientos según convenga. En grafos pequeños se puede analizar a mano; en mapas grandes se vuelve heurístico.
Para discutir en clase:
• Dibujad un grafo donde χ = 4 — ¿podéis hacerlo planar?
• El "grafo completo" K₄ necesita 4 colores. ¿Lo encontráis dentro de algún mapa?
• ¿Por qué no existe un mapa con χ = 5? (No es trivial — eso es el 4CT.)
• En Francia con 3 colores, ¿qué configuraciones de apertura llevan a un atasco rápido?
IA del modo difícil: minimax con poda α-β, profundidad adaptativa (4 en Francia, 3 en Map17, 2 en África) y evaluación basada en movilidad (jugadas legales restantes para cada bando). En mapas grandes el árbol de juego explota, así que la profundidad cae — un humano experto vence al hard, pero el IA es buen rival para nivel escolar.
Conexiones extra:
• Sudoku es un problema de coloreado de grafos disfrazado (9 colores).
• Asignación de frecuencias en torres de telefonía: el grafo es el de interferencias.
• Horarios escolares: los grupos que comparten alumnos son vecinos y no pueden compartir franja.