Resolviendo sudokus con lápices de colores

Que los grafos sirven para casi todo ya lo hemos dicho muchas veces en esta casa: desde desenmascarar fenómenos extraños en tu muro de Facebook hasta diseñar métodos de catas de alimentos o destronar a la khaleesi de 'Juego de tronos'. Lo dicho, sirven para (casi) todo. Sin embargo, una de las aplicaciones más llamativas tiene que ver con un grafo y una caja de colores. De hecho, también vimos ya cómo era posible organizar las mesas de un banquete de bodas sin conflictos usando eso: un grafo y una caja de colores.

Como estamos en verano, algunos de vacaciones, a menudo ocurre que si no estamos en uno de esos viajes agotadores en los que pretendemos ver cuatro países completos en quince días (hay una película de finales de los '70 al respecto, 'Si hoy es martes, esto es Bélgica') no sabemos cómo llenar nuestro tiempo de asueto. Hay horas (o situaciones familiares) en las que recurrimos al primer pasatiempo que tenemos a mano. Y seguro que alguno de los que hemos intentado solucionar es un sudoku (y si no, os animo a ello, que son francamente divertidos).

Pues bien, hoy vamos a aprender a resolver (y diseñar) sudokus usando grafos y lápices de colores. Quizaś ahora alguien se pregunte si existen métodos automáticos para solucionar sudokus, si hay algún programa de ordenador que los resuelva en un pispás. Y la verdad es que sí, existen varios programas que los resuelven, pero el que les proponemos hoy no sólo permite resolverlos, sino también diseñarlos.

La idea es pensar en un sudoku como un grafo (los mismos que usábamos, por ejemplo, para hablar de la paradoja de la amistad, de la ilusión de la mayoría o, incluso, de 'Juego de Tronos').

Un grafo se puede entender como un conjunto de puntos que llamamos vértices y unas líneas que unen a algunos de dichos puntos, de dos en dos, a las que llamamos aristas. Algo así:

Pueden pensar por ejemplo en Facebook: cada usuario sería un vértice y dos usuarios que sean amigos en esa red social estarían unidos por una arista.

Vamos a ver ahora cómo construir un grafo a partir de un sudoku y cómo resolver este coloreando sus vértices.

Para mostrar todo voy a trabajar con un sudoku infantil, de esos 4x4, aunque todo lo que diga es válido para uno normal 9x9 -eso sí, se hace más laborioso construirlo todo y nos podemos perder con la maraña de vértices y aristas-.

Supongamos así, que tenemos este sencillísimo sudoku:

Queremos asociarle un grafo. La idea es simple: primero construimos lo que llamaremos el sudoku base, un sudoku vacío al que le añadiremos después las restricciones. Así, nuestro grafo tendrá 16 vértices que numeramos del 0 al 15 (uno por cada cuadradito):

Ahora vamos a unir, mediante aristas, el vértice correspondiente al cuadradito 0 con todos los vértices que se corresponden con casillas que no pueden tener el mismo número que él: las que están en su fila (la fila de arriba), las que están en su misma columna (la columna de la izquierda) y las que están en su cuadradito (el superior izquierdo)

Repetimos el mismo proceso con todos los vértices para obtener este grafo, que es el que llamamos grafo base del sudoku:

Aunque parezca complicado, para un ordenador dicho grafo es bastante sencillo. Lo sería, incluso, el resultante de un sudoku 9x9.

Ahora vamos a usar colores. La idea es asignar colores a los vértices del grafo, de tal forma que si dos vértices comparten una arista no puedan tener el mismo color.

Ya hemos hablado de coloreado de grafos en este vídeo. En aquella ocasión, el grafo que coloreábamos representaba relaciones de incompatibilidad a la hora de compartir mesa en un banquete de bodas.

La idea es que podemos pintar el grafo base del sudoku usando cuatro colores e identificar cada color con un número, obteniendo así un sudoku. Lo curioso es que por cada coloración distinta podemos obtener un sudoku diferente, y os puedo asegurar que hay un montón.

Si lo que queremos es resolver el sudoku de nuestro ejemplo, tendremos que añadir nuevas aristas al grafo base. Nos fijamos en que si queremos que dos casillas tengan distinto número, queremos que sus vértices correspondientes tengan distinto color. Eso es muy simple: basta con unir esos dos vértices por una arista y así nos aseguramos de que nunca le vamos a asignar el mismo color.

En nuestro ejemplo, el vértice 1 del grafo base deberá unirse con el vértice 11 para que se le asignen colores distintos, porque con el 2, el 4, y el 13 ya lo está en el grafo base. De forma análoga, tendremos que unir el vértice 2 del grafo base con el 4 y con el 13 para asegurarnos de que tendrán colores distintos (las aristas del 2 al 1 y al 14 ya están en el grafo base del sudoku). Y así sucesivamente.

El siguiente y último paso es forzar a las casillas que tengan el mismo número a que al colorear los vértices correspondientes se les asigne el mismo color. Para ello, vamos a fijarnos en nuestro ejemplo: queremos que el vértice 1 y el 14 del grafo base tengan el mismo número (1) o el mismo color (amarillo), ¿cómo lo conseguimos?

Les dejo que lo piensen un poco.

Ya.

Efectivamente, si añado aristas desde el vértice 1 a los 3 que comparten fila con el vértice 14 ya lo tenemos: ninguno de esos tres vértices podrán colorearse como el 1, en amarillo, y la única opción que nos dejará para el 14 será esa, amarillo, como el 1.

Es decir, que añadimos aristas que unan al vértice 1 con los vértices 12 y 15, porque la arista del 1 al 13 está en el grafo base. Si el 12, el 13 y el 15 están unidos con el 1 ninguno de ellos usará el amarillo que será asignado, tachán, al 14. Sí, es chulísimo, lo sé.

Tendríamos que imponer ahora que los vértices 4 y 13 sean del mismo color repitiendo esta estrategia. Y por último, que sean también del mismo color los vértices 2 y 11.

Cuando tengan añadidas esas seis nuevas aristas al grafo base sólo tendrán que colorear los vértices del grafo que les ha quedado siguiendo las reglas: no usar más de cuatro colores y que los vértices del mismo color no pueden estar unidos con una arista.

Ya, lo sé. Están pensando que el sudoku del ejemplo se resuelve más rápido directamente y puede que sea verdad. Pero este método es fácil de implementar en un ordenador y con ello diseñar y resolver en segundos sudokus de mayor tamaño. Y, bueno, este también es más original para presumir de él en el chiringuito, ¿no?.