Resolviendo sudokus con backtracking en Python

Los sudokus es algo que siempre me ha llamado la atención y, cuando aprendí durante el grado en ingeniería informática, en las asignaturas de inteligencia artificial, lo que era el backtracking se me ocurrió la idea de resolver sudokus usando este método.

Es un problema muy divertido de resolver, así que quiero contarte hoy estos dos conceptos: lo que es un sudoku y lo que es el backtracking. Además, vamos a crear un programa que lo resuelva usando Python.

¿Qué es un soduku?

El Sudoku es lo que se conoce como un pasatiempo, un juego de lógica o rompecabezas con una base matemática, que en general es bastante popular (hay miles de apps). El problema consiste en resolver una cuadrícula (o vector/matriz) de 9x9 casillas, que se divide en subcuadrículas de 3x3, filas y columnas. El objetivo es rellenar la cuadrícula (las 9x9=81 casillas) con los números del 1 al 9 cumpliendo las siguientes normas:

• No se puede repetir ningún número en la misma fila.
• No se puede repetir ningún número en la misma columna.
• No se puede repetir ningún número en la misma subcuadrícula de 3x3.

Una partida, que suele tener un medidor de tiempo para saber cómo de rápido (o lento) lo resuelves, viene dada por una serie de números que vienen ya dados y tu objetivo es rellenar toda la cuadrícula usando la lógica y la deducción. Es algo así como un ajedrez simple, que te permite desarrollar diferentes tipos de pensamiento explorando las soluciones, descartando caminos del árbol de decisión y eligiendo las mejores soluciones potenciales.

¿Qué es backtracking?

El backtracking es una técnica utilizada en ciencias de la computación para solucionar problemas que tienen un conjunto de restricciones. La estrategia consiste en ir explorando el árbol de soluciones y, cuando estamos en un camino que no cumple con las restricciones (es inválido) entonces se descarta, se vuelve al estado anterior y se continúa. Lo bueno de esta técnica es que permite podar el árbol de soluciones evitando explorar ramas que no son válidas, lo que reduce el tiempo de ejecución.

Siempre que hablo de este tipo de problemas me gusta mencionar la notación O grande, ya que un algoritmo por ineficiente que sea, puede ser muy rápido cuando la entrada es pequeña, pero ser muy lento cuando la entrada de datos crece sólo un poco. Por tanto, según nuestro problema tendremos que evaluar qué opción es mejor.

El backtracking nos va a permitir ir probando soluciones por fuerza bruta en nuestro sudoku, y aquellas opciones que no satisfagan las restricciones del sudoku descartarán múltiples ramas del árbol de soluciones.

Si aplicamos combinatoria tenemos que en un soduku existen 81 casillas, y tenemos que rellenarlas con 9 grupos de números en el rango del 1 al 9] sin repetir. Esto nos da que un grupo lo puedes organizar de 9! formas, y hay que escoger 9 grupos, por lo que tenemos 9!^2 posibles soluciones de las cuales la mayoría no cumplirán las restricciones.

Lo bueno del backtracking es que permite descartar muchas de estas soluciones sin necesidad de explorarlas al completo, y por otro lado, estamos hablando de un número relativamente bajo de soluciones por lo que un ordenador debería explorarlo bastante rápido. Hay otros problemas que son mucho más complejos y que no permiten calcularse tan rápido como este, aunque de eso podemos hablar en otro post.

Resolviendo un sudoku con programación

Lo primero que tenemos que hacer es pensar cómo vamos a modelar la estructura de datos para poder realizar el backtracking. La idea es la siguiente:

Empezamos en la primera posición del sudoku. Para cada posición, comprobamos si la casilla ya viene dada o si tenemos que rellenarla. Si tenemos que rellenarla, probamos con el primer número (1) y comprobamos si es válido o no. Si no es válido incrementamos y comprobamos si es válido. Si llegamos al 9, entonces hemos llegado a una rama del árbol de soluciones que no es válida y tenemos que volver (backtracking) a la posición anterior, limpiando la casilla actual e incrementando la casilla anterior. Si es válido, pasamos a la casilla siguiente y repetimos.

Este sería nuestro algoritmo. La estructura de datos puede ser una matriz, un array... lo que sea más fácil. En mi caso creo que me voy a decidir por un array ya que hace que los cálculos sean más simples.

Por lo que, el programa constará de varias etapas:

1. Leer el fichero con los datos del sudoku. Que además, hay sudokus con distintos niveles de dificultad, por lo que siempre empezaremos por alguno simple.
2. Comenzamos con el algoritmo probando soluciones.
3. Validamos la fila, columna y la submatriz de 3x3.
4. Repetimos hasta que el programa termine (si nos hemos equivocado se quedará en bucle).

La verdad es que la idea es simple y lo siguiente que puedes hacer es probar a resovlerlo tú, ver el código en el siguiente repositorio de GitHub o ver el vídeo de youtube al inicio del vídeo donde construyo la solución en directo.