Solucionador de Sudoku Python

1. Use el algoritmo de retroceso en Python para resolver Sudoku
2. Conclusión

Sudoku es un juego de rompecabezas de colocación de números basado en la lógica que es más popular entre las personas que están enamoradas de la lógica y el razonamiento. Resolver sudokus ayuda al cerebro a mejorar la concentración y el pensamiento lógico.

Este artículo describe cómo podemos resolver sudoku usando Python.

Use el algoritmo de retroceso en Python para resolver Sudoku

Cuando buscamos soluciones para problemas computacionales, el algoritmo de retroceso es la técnica que usamos con frecuencia. Mientras resuelve sudoku, comprueba si los dígitos de las casillas llenas son válidos o no.

Si no es válido, comprueba otros números del 1 al 9. Si no encuentra ningún dígito válido, retrocede a la opción anterior.

Cuando llegamos a un callejón sin salida y volvemos a la elección anterior, hemos hecho y cambiaremos nuestra elección, dando como resultado una posible solución diferente.

Tomemos el enfoque de implementar el solucionador de sudoku junto con el algoritmo de retroceso.

Primero, tenemos que armar el tablero formando el rompecabezas.

def setBoardFunc(puz):
    global grid
    print("\n---------------Sudoku Solver---------------\n")
    print("Here is the Sudoku Problem :")
    for i in range(0, len(puz), 9):
        row = puz[i : i + 9]
        temp = []
        for block in row:
            temp.append(int(block))
        grid.append(temp)
    printGridFunc()

Aquí, he definido una función llamada setBoardFunc() para formar el rompecabezas. Durante el bucle, establece un rompecabezas de 9x9 e inicializa las celdas vacías con 0.

Después de completar las operaciones de las funciones, imprime la entrada dada en el puz. Luego tenemos que imprimir la grilla; este paso imprime la cuadrícula de 9x9 con las entradas dadas.

def printGridFunc():
    global grid
    for row in grid:
        print(row)

A continuación, comprobaremos si el valor actual puede colocarse dentro del cuadro actual.

def checkValidFunc(row, column, num):
    global grid
    for i in range(0, 9):
        if grid[row][i] == num:
            return False
    for i in range(0, 9):
        if grid[i][column] == num:
            return False
    square_row = (row // 3) * 3
    square_col = (column // 3) * 3
    for i in range(0, 3):
        for j in range(0, 3):
            if grid[square_row + i][square_col + j] == num:
                return False
    return True

Este paso verifica si el número dado es válido para el cuadro en particular. El número no debe ser ninguno de los cuadros de la misma fila, columna o bloque de cuadros para colocar en el lugar actual.

Si el número cumple ese requisito y devuelve true, podemos pasar al siguiente valor; si no, el número es rechazado. Luego tenemos que recorrer todos los bloques adaptándonos al algoritmo de retroceso.

def solveFunc():
    global grid
    for row in range(9):
        for column in range(9):
            if grid[row][column] == 0:
                for num in range(1, 10):
                    if checkValidFunc(row, column, num):
                        grid[row][column] = num
                        solveFunc()
                        grid[row][column] = 0
                return
    print("\nSolution for the Sudoku Problem: ")
    printGridFunc()

La última parte de este fragmento de código comprueba si el número es válido o no. Aquí, ha introducido el algoritmo de seguimiento de funciones.

Al principio, busca una celda vacía; si lo encuentra, el sudoku resuelto está ahí, e imprime la solución del sudoku dado. Si encontraba alguna casilla vacía, adivinaría un número del 1 al 9 iterando.

Si existe un número válido, llama a solveFunc() y pasa a la siguiente celda vacía, pero si ninguna de las conjeturas es válida, la llamada anterior de la función restablecerá el valor de la celda a 0 y continuará iterando para encontrar el siguiente número válido.

Cuando el algoritmo llena las casillas vacías con números válidos hasta el callejón sin salida, retrocede el proceso y repite todo el proceso. Por último, pasemos la grilla y llamemos a la función para resolver el sudoku dado.

puz = (
    "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
)
grid = []
setBoardFunc(puz)
solveFunc()

Código fuente completo:

def setBoardFunc(puz):
    global grid
    print("\n---------------Sudoku Solver---------------\n")
    print("Here is the Sudoku Problem :")
    for i in range(0, len(puz), 9):
        row = puz[i : i + 9]
        temp = []
        for block in row:
            temp.append(int(block))
        grid.append(temp)
    printGridFunc()


def printGridFunc():
    global grid
    for row in grid:
        print(row)


def checkValidFunc(row, column, num):
    global grid
    for i in range(0, 9):
        if grid[row][i] == num:
            return False
    for i in range(0, 9):
        if grid[i][column] == num:
            return False
    square_row = (row // 3) * 3
    square_col = (column // 3) * 3
    for i in range(0, 3):
        for j in range(0, 3):
            if grid[square_row + i][square_col + j] == num:
                return False
    return True


def solveFunc():
    global grid
    for row in range(9):
        for column in range(9):
            if grid[row][column] == 0:
                for num in range(1, 10):
                    if checkValidFunc(row, column, num):
                        grid[row][column] = num
                        solveFunc()
                        grid[row][column] = 0
                return
    print("\nSolution for the Sudoku Problem: ")
    printGridFunc()


puz = (
    "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
)
grid = []
setBoardFunc(puz)
solveFunc()

Producción:

Conclusión

Aunque hay más formas de resolverlo, el uso del algoritmo de retroceso hace que el resultado final del sudoku sea más preciso, pero lleva más tiempo, ya que consta de muchas iteraciones. Sin embargo, resolver sudokus mejora el pensamiento lógico de una persona y es una forma emocionante de pasar el tiempo libre.