Creación de un algoritmo de resolución de sudokus

Ahora que conocemos el juego y sus formas de resolverlo en profundidad, tenemos que intentar crear un algoritmo que pueda resolver sudokus de manera eficiente. He elegido Python como lenguaje de programación debido a su facilidad de uso.

Inserción de los datos

Lógicamente, para que el programa funcione, tenemos que averiguar un método eficiente para insertar nuestros datos.

Como el programa se va a encargar de resolver sudokus, creo que la manera más fácil de insertar el problema en el programa es que vaya preguntando por el número que está en cada celda.

Por ejemplo, si queremos insertar el siguiente sudoku, escribiremos lo siguiente:

Datos por filas:
> 530070000
> 600195000
> 098000060
> 800060003
> 400803001
> 700020006
...

Escribiremos 0 si la celda está vacía, y los datos serán almacenados en una matriz de Python, básicamente una lista con listas. Un ejemplo de código sería este:

filas = int(input("Filas: "))
columnas = int(input("Columnas: "))

matrix = [] 
print("Datos por filas:")

for i in range(filas):   
    while True:
        # Pedimos al usuario que ingrese los números para la fila, sin espacios
        fila_str = input(f"Ingrese los {columnas} números para la fila {i+1} (sin espacios): ")
        if len(fila_str) == columnas:  # Verificamos que la longitud de la cadena coincida con el número de columnas
            # Convertimos la cadena en una lista de enteros
            fila = [int(c) for c in fila_str]
            matrix.append(fila)
            break
        else:
            print(f"Error: Debes ingresar exactamente {columnas} números, sin espacios.")

# Mostrar la matriz
print("\nLa matriz es:")

for i in range(filas):
    for j in range(columnas):
        print(matrix[i][j], end=" ")
    print()

Algoritmo de resolución

Para que el programa resuelva el sudoku, debemos establecer un orden de ejecución de los diferentes métodos de resolución. Todos ellos se basan en encontrar los números candidatos, es decir, eliminar los números que estén en la misma fila, columna o bloque, o campo que estemos analizando. Por lo tanto, el primer paso será el análisis de candidatos.

1. Análisis de candidatos.

Para analizar los candidatos de una celda, debemos asumir que son candidatos todos los posibles números, es decir, del 1 al 9. Después, escanearemos la fila, columna y campo en la que está el número, y eliminaremos los números que encontremos. Por ejemplo, para el primer campo vacío, en a3, eliminaríamos los números 5,3,7,6,9, y 8, y así sucesivamente con todos los números. Tras hacer eso, nos quedaría algo así:

Como puedes ver, hay ocasiones en las que nos queda sólo un número candidato, por lo que podemos rellenarlo, lo que va a causar que se eliminen más candidatos en otras celdas, de hecho este ejemplo se puede resolver entero utilizando este método. Este sería el proceso del algoritmo de candidatos en orden:

1. El programa debe ir escaneando cada celda, y recolectar los números que están en su misma columna, fila y campo.
2. Después, eliminará cada número que haya encontrado en esos lugares.
   1. Si sólo se queda con un número, entonces asignará ese número a ese campo, y continuará al siguiente.
   2. En cambio, si se queda con varios números, saltará al siguiente, y repetirá el proceso.
3. Este proceso se repetirá hasta que no se puedan rellenar más celdas,y tras ello, imprimirá los resultados.

---

Pero, qué ocurre si nos quedamos sin candidatos?

2. Análisis de parejas, tríos y cuartetos desnudos

Veamos este ejemplo:

Aquí ya hemos aplicado el primer paso del algoritmo, y todavía nos quedan muchos huecos. ¿Qué hacemos?

La pareja de números que hay resaltada en azul se llama "par desnudo", es decir, es una pareja de números candidatos que comparten la misma unidad, es decir: la misma fila, columna o blloque. Cuando esto ocurre, sabemos que un número va a estar en una casilla y el otro en la otra, y, aunque no sabemos cuál de los dos está en qué casilla, podemos eliminar los dos de la unidad correspondiente, en este caso, del mismo campo. En este caso, eliminamos el 9 del campo resaltado en verde, lo que nos deja con una sola posibilidad, el 1. Ahora, veamos este ejemplo:

En el siguiente diagrama existen dos tríos desnudos, es decir, son conjuntos de celdas que pertenecen a la misma unidad y tienen en total 3 números candidatos diferentes. Cuando esto ocrurre, podemos eliminar esos números de la misma unidad a la que pertenecen, en este caso son filas. El primer trío es el resaltado en verde, y podríamos quitar el número 9 del campo en morado, y el segundo trío es el resaltado en naranja y el resaltado en morado, y podríamos quitar el número 9 de la celda resaltada en rojo. Este caso es curioso, ya que si aplicamos un trío, el otro se convierte en una pareja desnuda, pero el resultado es el mismo. Ahora veamos el siguiente ejemplo:

En este ejemplo, las cuatro celdas resaltadas en verde son cuartetos desnudos, que siguen la misma lógica de los tríos y parejas desnudas. En este caso, podemos eliminar el 2 y el 3 de la celda azul. No hay nada más allá de los cuartetos, ya que hay 9 números, y que haya un "quinteto", implicaría que hay cuarteto complementario.

3. Descartes

Ahora veamos este ejemplo:

Aquí podemos ver que en este bloque se puede escribir un número por descarte, ya que el único posible número donde puede ir el 9 es en la casilla marcada en verde.

4. Fuerza Bruta

Es posible que el sudoku se quede con algunos huecos que no se pueden resolver por ninguno de los métodos anteriores, así que tras esto utilizaremos el método de fuerza bruta, o "brute-force". La variante de este método que vamos a utilizar es el llamado "búsqueda en profundidad", o "depth-first search", que analiza cada posible "rama" de soluciones hasta el final, antes de pasar a la siguiente, de la siguiente manera:

Aunque esto pueda parecer muy ineficiente, en realidad no lo es tanto, ya que las opciones que quedarán tras resolver el sudoku de forma analítica serían bastantes menos. Por ejemplo, el sudoku de los ejemplos anteriores se puede resolver únicamente con los métodos sistemáticos.

Resumen

En conclusión, un algoritmo de resolución de sudokus relativamente avanzado tenría los siguientes procesos en el siguiente orden de prioridad:

1. Análisis de candidatos
2. Análisis de parejas, tríos y cuartetos desnudos
3. Descartes
4. Fuerza Bruta

Lógicamente, tras cada "pasada" de escaneo de celdas se deben reevaluar los candidatos y empezar por el primer método de nuevo. Esto significa que el programa funcionaría en bucle hasta que se haya resuelto el sudoku. Aquí tenemos un diagrama de flujo que representa el funcionamiento del programa:

Sin embargo, el mundo de los sudokus es muy extenso y se han creado sudokus con una dificulad extrema, y eso conlleva la creación de algoritmos de resolución mucho más complejos que incorporan métodos mucho más avanzados.

Aquí puedes ver un algoritmo de resolución de sudokus extremadamente complejo, que incorpora hasta 39 métodos diferentes.