Solucionador de sudokus
Contents
3. Solucionador de sudokus¶
Este capítulo, más que desarrollar un código jugable, te proponemos la resolución de un problema matemático planteado como un juego. En concreto, el universalmente conocido sudoku. Si no has jugado nunca, seguro que has oído hablar de él. Las reglas son muy sencillas:
El objetivo del sudoku es rellenar una cuadrícula de 9 × 9 celdas dividida en subcuadrículas de 3 × 3
Hay que colocar las cifras del 1 al 9 en las celdas vacias partiendo de algunos números ya dispuestos en la cuadrícula
Las cifras no se pueden repetir en una misma fila, columna o subcuadrícula
Como siempre, os planteamos una solución sencilla y os animamos a mejorar nuestra implementación al final del capítulo.
See also
Puedes encontrar más información sobre los orígnes y las variantes del sudoku aquí. Aunque la mejor forma de entender el juego, es jugando!. Una rápida búsqueda en Goolge devuelve múltiples páginas para jugar online como sudoku.com
3.1. Construir el tablero¶
Vamos a comenzar implementando una función print_board(board) que recibe como único argumento el tablero del sudoku planteado y lo saca por pantalla. Los valores con los que vamos a jugar se le pasaran en una variable board que contiene una lista de listas como la siguiente:
board = [[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,7,4,0,0],
[0,4,9,2,0,6,0,0,7]]
En el ejemplo anterior, los ceros indican las casillas vacías que tenemos que rellenar. La función print_board(board) no devuelve ningun valor, sólamente saca por pantalla los valores del sudoku utilizando el caracter ? para indicar una casilla libre.
A modo de ejemplo vamos a invocar a la función con el tablero propuesto:
print_board(board)
7 8 ? | 4 ? ? | 1 2 ?
6 ? ? | ? 7 5 | ? ? 9
? ? ? | 6 ? 1 | ? 7 8
- - - - - - - - - - -
? ? 7 | ? 4 ? | 2 6 ?
? ? 1 | ? 5 ? | 9 3 ?
9 ? 4 | ? 6 ? | ? ? 5
- - - - - - - - - - -
? 7 ? | 3 ? ? | ? 1 2
1 2 ? | ? ? 7 | 4 ? ?
? 4 9 | 2 ? 6 | ? ? 7
Solución:¶
def print_board(board):
for i in range(len(board)):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - -")
for j in range(len(board[0])):
value=str(board[i][j])
if value=="0":
value="?"
if j % 3 == 0 and j != 0:
print("| ", end="")
if j == 8:
print(value)
else:
print(value + " ", end="")
Note
La implementación de esta función utiliza un esquema clásico de bucles anidados para recorre la cuadrícula por filas (bucle for sobre la variable i) y por columnas (bucle for sobre la variable j). El chequeo de los índices i y j permite detectar cuando hay que generar una línea discontínua o cuando hay que aliminar el salto de línea del comando print.
Este tipo de solución es muy habitual cuando tenemos que trabajar con listas anidadas.
3.2. Detectar casillas vacías¶
El siguiente paso es crear una función find_empty(board) que recibe la misma variable board que la función print_board. Esta variable es una lista de listas que contiene los valores del sudoku y los huecos. La función find_empty(board) debe devolver las coordenadas (i,j) del primer hueco que encuentre. El orden para recorrer el tablero será, de nuevo, recorrer todas las columnas para cada fila. En caso de que el código revise todo el tablero sin encontrar ningún hueco, la función devolverá None.
Solución:¶
def find_empty(board):
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 0:
return (i, j) # row, col
return None
Vamos a probar que funciona correctamente pasándole el tablero anterior. La función debería devolver las coordenadas (0,2) correspondientes con la primera fila y la tercera columna (recuerda que en python los índices empiezan en 0).
board = [[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,7,4,0,0],
[0,4,9,2,0,6,0,0,7]]
out=find_empty(board)
print(out)
(0, 2)
Y si probamos su ejecución con el tablero resuleto, la función debería devolver None.
board = [[7, 8, 5, 4, 3, 9, 1, 2, 6],
[6, 1, 2, 8, 7, 5, 3, 4, 9],
[4, 9, 3, 6, 2, 1, 5, 7, 8],
[8, 5, 7, 9, 4, 3, 2, 6, 1],
[2, 6, 1, 7, 5, 8, 9, 3, 4],
[9, 3, 4, 1, 6, 2, 7, 8, 5],
[5, 7, 8, 3, 9, 4, 6, 1, 2],
[1, 2, 6, 5, 8, 7, 4, 9, 3],
[3, 4, 9, 2, 1, 6, 8, 5, 7]]
out=find_empty(board)
print(out)
None
3.3. Validación de candidatos¶
La función más importante de nuestro código es la función que chequea si un número candidato para una determinada posición vacía cumple las reglas del sudoku. Para ello vamos a implementar la función valid(board, num, pos) que recibe los siguientes argumentos:
board con la lista de listas que representa los valores del tablero del sudoku
num numero entero candidato
pos tupla con las coordinedas de la posición que pretendemos ocupar con num
Recuerda que para que para validar un número en una celda de nuestro sudoku, este número debe aparecer una sóla vez en la fila y en la columna en la que se está intentando insertar. Además, el tablero de sudoku está divido en subcuadrículas de 3x3 en las que el número también debe ser único.
Por ejemplo, si partimos de este tablero:
board = [[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,7,4,0,0],
[0,4,9,2,0,6,0,0,7]]
Colocar un 8 en la fila 1, columna 3 debería fallar por reptir el valor 8 dentro de la misma fila:
valid(board,8,(0,2))
False
Colocar un 6 en la fila 3, columna 0 debería fallar por reptir el valor 6 dentro de la misma columna:
valid(board,6,(2,0))
False
Colocar un 6 en la fila 3, columna 3 debería fallar por reptir el valor 6 dentro de la misma cuadrícula:
valid(board,6,(2,2))
False
Sin embargo, colocar un 3 en esa misma posición (2,2) no debería alterar ninguna de las normas del sudoku:
valid(board,3,(2,2))
True
Solución:¶
def valid(board, num, pos):
# Check row
for i in range(len(board[0])):
if board[pos[0]][i] == num:
return False
# Check column
for i in range(len(board)):
if board[i][pos[1]] == num:
return False
# Check box
box_x = pos[1] // 3
box_y = pos[0] // 3
for i in range(box_y*3, box_y*3 + 3):
for j in range(box_x * 3, box_x*3 + 3):
if board[i][j] == num:
return False
return True
3.4. Implementa el solucionador¶
A estas alturas ya disponemos de todas las piezas necesarias para resolver el sudoku. Sólo nos queda convinarlas adecuadamente para ir dando valores a las casillas vacías sin violar las reglas del juego. Para ello, vamos a construir una función solver(board) que va a recibir la variable con la lista de listas que contiene los valores del sudoku. La función devolverá True si el sudoku se ha resuelto o False en caso de que queden casillas por resolver.
El razonamiento es el siguiente:
Encontrar la primera posición vacia del sudoku
Usar la función valid para comprobar si un número es aceptado en una posición determinada
Usar esta información para cambiar los valores de cada una de las casillas vacias
Tip
Tip Usar recurrencia ayuda mucho para solucionar este problema
Warning
Recuerda que cuando una lista ser pasa como argumento de una función y esa misma lista se modifica en el interior de la función, la lista original también se modifica. Por ejemplo:
def changeList(x):
x[0]="a"
collection = [1,2,3]
print(collection)
[1, 2, 3]
changeList(collection)
print(collection)
[‘a’, 2, 3]
Solución:¶
def solve(board):
empty = find_empty(board)
if not empty:
return True
else:
row, col = empty
for i in range(1,len(board)+1):
if valid(board, i, (row, col)):
board[row][col] = i
if solve(board):
return True
else:
board[row][col] = 0
return False
Como siempre hacemos, te recomendamos que pruebes su funcionamiento para asegurate. de que la función hace lo que le pedimos. Vamos a partir del tablero con huecos:
board = [[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,7,4,0,0],
[0,4,9,2,0,6,0,0,7]]
print_board(board)
7 8 ? | 4 ? ? | 1 2 ?
6 ? ? | ? 7 5 | ? ? 9
? ? ? | 6 ? 1 | ? 7 8
- - - - - - - - - - -
? ? 7 | ? 4 ? | 2 6 ?
? ? 1 | ? 5 ? | 9 3 ?
9 ? 4 | ? 6 ? | ? ? 5
- - - - - - - - - - -
? 7 ? | 3 ? ? | ? 1 2
1 2 ? | ? ? 7 | 4 ? ?
? 4 9 | 2 ? 6 | ? ? 7
Ahora vamos a invocar a la función solucionadora. Nota que la función solucionadora sólo devuelve una variable booleana, el tablero se actualiza en la misma variable que le pasas como argumento.
solve(board)
True
print_board(board)
7 8 5 | 4 3 9 | 1 2 6
6 1 2 | 8 7 5 | 3 4 9
4 9 3 | 6 2 1 | 5 7 8
- - - - - - - - - - -
8 5 7 | 9 4 3 | 2 6 1
2 6 1 | 7 5 8 | 9 3 4
9 3 4 | 1 6 2 | 7 8 5
- - - - - - - - - - -
5 7 8 | 3 9 4 | 6 1 2
1 2 6 | 5 8 7 | 4 9 3
3 4 9 | 2 1 6 | 8 5 7
3.5. Extensiones del Juego¶
Después de lo visto en este capítulo, seguro que se te ocurren muchas ideas para mejorar el funcionamiento y la jugabilidad. Algunas sujerencias son:
Utiliza la librería numpy para reemplazar el uso de lista de listas
Puedes intentar optimizar el código evitando que la función solver pruebe todos los números entre el 0 y el 9. Es decir, si estamos buscando un candidato para la posición (i,j), podemos ver qué numeros se han usado en la fila i y en la columna j para evitar tener que probarlos, ya que su uso violaría las normas del sudoku. Esta mejora no está justificada por motivos de performance porque la computación de nuestro código es muy sencilla, pero es un buen ejercicio de habilidad programadora
Échale un vistazo a diferentes variabtes del sudoko aquí. Algunas con números y otras con letras, e intenta implementar la que más te motive.