Estudie este código detenidamente y descubra una forma inteligente de utilizar la recursividad para resolver esos complicados sudokus.
Sudoku es un rompecabezas numérico popular que consiste en una cuadrícula de 9x9 con dígitos del 1 al 9. El rompecabezas incluye una combinación de números y algunos espacios vacíos, que debes llenar.
Al completar los espacios vacíos, cada fila, columna y subcuadrícula de 3x3 debe contener todos los dígitos del 1 al 9.
Un simple script de Python puede ayudarte a resolver un rompecabezas de Sudoku. Puede analizar todos los espacios vacíos en el tablero de Sudoku y encontrar un posible número para llenar cada espacio en blanco.
Cómo crear y mostrar el tablero de Sudoku
Dentro de una secuencia de comandos de Python, deberá usar una lista de matrices para almacenar los valores del rompecabezas de Sudoku sin resolver.
El código utilizado en este proyecto está disponible en este repositorio de GitHub bajo la licencia del MIT.
- Dentro de un nuevo script de Python llamado sudoku.py, almacene todos los valores para la cuadrícula de 9x9. Cada fila y columna representa los nueve números a través y hacia abajo del rompecabezas de Sudoku. Agregue 0 para representar los espacios que necesitan resolverse:
tablero = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
] - Dentro de una nueva función llamada print_board, usar un bucle for para procesar cada fila en la grilla:
definitivamenteimprimir_tablero(junta):
para fila en rango(9): - Para separar cada fila en tercios, verifique si la fila es divisible por tres y agregue una línea:
si fila % 3 == 0y fila != 0:
imprimir("- - - - - - - - - - - - - - ") - Dentro de cada fila, recorra cada columna. También puede dividir columnas en tercios comprobando si la columna es divisible por tres:
para columna en rango(9):
si col % 3 == 0y columna != 0:
imprimir(" | ", fin="") - Imprime el valor numérico almacenado en la cuadrícula. Si la columna es la última columna de esa fila en particular, agregue una línea de ruptura, de modo que la siguiente fila aparezca en una nueva línea:
si columna == 8:
imprimir (tablero [fila] [columna])
demás:
imprimir (str (tablero [fila] [columna]) + " ", fin="") - Llame a la función para imprimir el tablero:
print_board (tablero) - En una línea de comando, navegue a la carpeta donde almacenó su secuencia de comandos de python, por ejemplo:
cd de escritorio - Use el comando python para ejecutar su script de Sudoku. Ver el rompecabezas impreso en la pantalla:
python sudoku.py
Cómo identificar los espacios vacíos para resolver
Puede recorrer las listas para encontrar los espacios que constan de ceros. Estos determinan qué espacios necesitan ser resueltos.
- En una nueva función llamada find_empty(), recorra cada fila y columna en el tablero:
definitivamenteencontrar_vacío(junta):
para fila en rango(9):
para columna en rango(9): - Si el valor de la celda actual es 0, devuelve la posición actual de la celda vacía:
si tablero[fila][columna] == 0:
devolver (fila, columna) - Si la secuencia de comandos llega al final de la función, eso significa que la secuencia de comandos no pudo encontrar ninguna celda con el valor de 0. En este caso, no devolver nada:
devolverNinguno - En una nueva función llamada solve(), use la función de búsqueda para encontrar el primer espacio vacío en el tablero:
definitivamenteresolver(junta):
encontrar = encontrar_vacío (tablero) - La función find_empty() devuelve la posición de la celda en formato de tupla, por ejemplo, (0, 2). Guarde estos valores por separado en el fila y columna variables De lo contrario, devuelva verdadero para indicar que no quedan espacios vacíos para resolver:
sino encontrar:
devolverVerdadero
demás:
fila, columna = encontrar
Cómo resolver el rompecabezas para cada fila, columna y cuadrícula de 3x3
Ahora que puede identificar el primer espacio vacío para resolver, deberá intentar encontrar un número apropiado para llenar ese espacio y resolver el rompecabezas.
usando la recursividad, llame a la función solve() dentro de sí misma para probar todas las combinaciones posibles de valores para todos los demás espacios también.
- Dentro de la función solve(), después de encontrar el primer espacio vacío, recorra cada número del 1 al 9. Estos números representan los posibles números que podrían llenar el espacio sin resolver:
para número en rango(1, 10): - Ingrese el tablero, el número posible y la posición de la celda vacía en una nueva función. La nueva función devolverá verdadero si ese número es un número válido que puede resolver ese espacio vacío. Si es válido, asigna ese número a la celda del tablero:
si is_valid (tablero, num, (fila, columna)):
tablero[fila][columna] = num - Cree la función is_valid(), con parámetros coincidentes:
definitivamentees válida(tablero, num, pos): - Use la función para verificar si colocar el número en esa posición viola alguna regla del juego Sudoku. Primero, verifique si ese número ya existe en la fila o columna de la celda:
para columna en rango(9):
si tablero[pos[0]][columna] == número y pos[1] != columna:
devolverFALSOpara fila en rango(9):
si tablero[fila][pos[1]] == número y pos[0] != fila:
devolverFALSO - Obtenga la cuadrícula de 3x3 a la que pertenece la celda. Puedes hacer esto dividiendo la posición de la celda por tres:
fila_caja = pos[0] // 3
caja_col = pos[1] // 3 - Para cada fila y columna en esa cuadrícula de 3x3, verifique si el número ya existe. Si es así, devuelve falso:
para fila en rango (box_row*3, fila_caja*3 + 3):
para columna en rango (box_col*3, caja_col*3 + 3):
si tablero[fila][columna] == num y (fila, columna) != pos:
devolverFALSO - Si el script llega al final de la función, eso significa que ninguna de las reglas de Sudoku falló. Devolver verdadero:
devolverVerdadero - La función is_valid() solo verifica si la ubicación del número es válida, pero eso no significa que sea la respuesta correcta a la solución general. Dentro de la función solve(), vuelva a llamar a la función solve() con el tablero actualizado. La función solve() puede llegar a un estado en el que ya no puede usar ningún número para llenar ningún espacio. En este caso, la función completa devuelve falso, restablece esa celda en particular a 0 y retrocede. La función solve() solo devuelve verdadero cuando el script puede llenar todos los espacios:
para número en rango(1, 10):
si is_valid (tablero, num, (fila, columna)):
tablero[fila][columna] = num
si resolver (tablero):
devolverVerdadero
tablero[fila][columna] = 0devolverFALSO - Para comenzar a resolver el rompecabezas, llame a la función solve() con el tablero original, en la parte inferior del script, después de declarar la función solve():
resolver (tablero) - Imprime el resultado final:
imprimir("Resuelto:")
print_board (tablero) - En la línea de comando, use el comando python para volver a ejecutar el script. Ver el rompecabezas resuelto impreso en la pantalla:
python sudoku.py
Crear juegos usando Python
Sudoku es solo uno de los muchos juegos que puedes crear y resolver usando Python. Puede usar Python para crear varios otros juegos, como un revoltijo de palabras, un juego de aventuras basado en texto o un juego de colores, por nombrar solo algunos.