Astronomía, divulgación, descubrimientos, ecología, innovación...
LA TEORÍA DE GRAFOS APLICADA AL AJEDREZ
Desde hace exactamente una semana, hablar de reyes y demás se ha convertido en un tema recurrente en las conversaciones de café y en las redes sociales. Se habla más de reyes que en las vísperas del 5 de enero. Nos hemos querido subir al carro de esta tendencia pero con un asunto más simple y lúdico que el debate sobre la continuidad impuesta de un sistema tan medieval como la monarquía o la necesidad de una consulta, en pleno siglo XXI, a los ciudadanos.
Vamos a pensar, como decíamos en la introducción, en el tablero del ajedrez (de cuyos orígenes ya contamos aquí una leyenda) y en la figura del rey.
¿Cuántos reyes como máximo se pueden colocar en el tablero de un ajedrez sin que se amenacen?
¿Cómo se resuelve? La forma más elegante, para mi gusto de verlo, es usando Teoría de Grafos, que como ya saben los lectores habituales de esta sección, es más apañada que un jarrillo de lata: lo mismo te soluciona un banquete de boda, que te pronostica la final del mundial de fútbol o te ayuda a diseñar los planos del metro.
Para el problema del rey del ajedrez podemos pensar en un grafo que tiene un vértice por cada casilla del tablero y una arista entre dos vértices (casillas) si es posible llegar de una a otra con un movimiento del rey. Si lo dibujamos para un tablero 4 x 4, por ejemplo, nos quedaría:
Resolver el problema de colocar el máximo número de reyes posibles en este, o cualquier otro tablero, consiste en encontrar el mayor conjunto independiente de vértices del grafo. Un conjunto de vértices de un grafo es independiente si ninguno de ellos está conectado entre sí. En el lenguaje del ajedrez, ninguno de ellos está amenazado por otro rey.
En realidad, el problema de encontrar el mayor conjunto independiente de un grafo en general es un problema NP-duro (muy informalmente, si un problema es NP-duro se supone que cualquier algortimo que lo resuelva tardará mucho en encontrar la respuesta). Pero para el grafo asociado al ajedrez podemos tratar de resolverlo directamente.
Si empiezan en una esquina y van coloreando con otro color los vértices en los que van colocando los reyes, pueden comprobar que no se pueden poner más de 4. Si quieren, pueden comenzar en otra casilla distinta y llegarán a la misma conclusión.
Este es un problema matemático clásico y sí, si lo piensan la respuesta, para un tablero de 8 x 8, es 16, como pueden ver en la figura:
De hecho, se conoce la fórmula para cualquier tablero de dimensiones n x n: si n es par, el número máximo de reyes que se pueden colocar es n² /4; si n es impar, el máximo es (n+1)² /4.
Un problema similar pero diferente, también con el rey sería el siguiente: ¿cuál es el número mínimo de reyes que necesito colocar en un tablero para que cualquier casilla de este esté amenazada por uno de ellos?
En esta ocasión, de lo que se trata es de encontrar el menor conjunto dominante de vértices del grafo. Un conjunto S de vértices de un grafo es dominante si cualquier otro vértice del grafo, fuera de este conjunto, está unido a uno de S. Dicho en términos del ajedrez, un conjunto de posiciones del rey es dominante si cualquier casilla del tablero (distinta de las usadas por los reyes) está amenazada un rey.
Vamos, entonces, a buscar el menor conjunto dominante del grafo 4 x 4. Les advierto que encontrar el menor conjunto dominante en un grafo es un problema NP-duro, pero en este ejemplo, también se puede hacer a mano.
Colocamos el primer rey en una zona en la que domine al mayor número de casillas:
Y después tratamos de dominar el resto de casillas, llegando a la conclusión de que necesitamos, como mínimo, 4 reyes.
¿Y en el tablero 8 x 8 de ajedrez? Eso se los dejo como ejercicio para la hora del bocata. Pero les tiene que salir 9.
Déjenme que les cuente otra aplicaciones de los conjuntos independientes y dominantes que también tienen que ver con juegos. Si encontramos un conjunto de vértices dominante (conectado con cualquier vértice del grafo) e independiente (los vértices de dicho conjunto no están conectados entre sí), tenemos lo que se conoce como el núcleo del grafo. Pues bien, conocer el núcleo de un grafo nos permite diseñar estrategias ganadoras para muchos juegos, nuestra amiga Mati nos cuenta algunos en esta mateaventura.
Pero volvamos al ajedrez. Si les gustan los acertijos como el del rey con tableros y fichas de ajedrez, les propongo unos cuantos (para el tablero 8 x 8, ¿eh?).
¿Cuál es el número máximo de torres que se pueden colocar en el tablero de forma que no se amenacen entre ellas? ¿Y el número máximo de reinas sin que se amenacen.
¿Cuál es el número mínimo de torres que dominan el tablero? ¿Y el número mínimo de alfiles? ¿Y de damas?
Piénsenlo un poco y desconecten un rato del mundo. Si se rinden, las soluciones están aquí.