Blog
Solucionador de Sudokus en Python
No hay comentarios
Sudoku es un juego de lógica japonés en donde el objetivo es rellenar una celda de 9×9 casillas con números del 1 al 9, de manera que cada columna, fila y cada uno de las subceldas 3×3 que componen la celda 9×9 contengan cada número solo una vez. Frente al obvio reto matemático y lógico que este juego representa, no es de extrañar que se hayan desarrollado programas que ayuden a resolver sudokus a traves de algoritmos. En este artículo estaremos desarrollando un solucionador de Sudokus en Python.
En el siguiente script se desarrolla un solcionador de Sudokus escrito en Python 3, se definen 8 funciones, contando la función main() en la cual se ejecuta el código principal del script:
from random import choice
def number_in_row(grid, row, number):
"""
Chequear si un número se encuentra en la fila especificada.
"""
return number in grid[row]
def number_in_col(grid, col, number):
"""
Chequear si un número se encuentra en la columna especificada.
"""
return number in (row[col] for row in grid)
def number_in_box(grid, row, col, number):
"""
Chequear si un número se encuentra en la caja a la que
corresponde la posición especificada.
"""
# Obtener la caja a la que pertenece el número.
box_row, box_col = box_by_pos(row, col)
# Construir una lista con los números en la caja.
numbers_in_box = unpack(
row[box_col*3:box_col*3 + 3]
for row in grid[box_row*3:box_row*3 + 3]
)
return number in numbers_in_box
def reduce(n):
"""
Reducir la posición 9x9 a 3x3.
"""
n /= 3
if n == 0 or n != int(n):
n += 1
return int(n)
def box_by_pos(row, col):
# Trabajar temporalmente con base 1.
row += 1
col += 1
# Obtener base 0 nuevamente.
return reduce(row) - 1, reduce(col) - 1
def unpack(iterable):
"""
>>> list(unpack([[1, 2], [3, 4]]))
[1, 2, 3, 4]
"""
for item in iterable:
yield from item
def get_possible_numbers(grid, row, col):
"""
Retorna números posibles para una determinada posición.
"""
for number in range(1, 10):
if (not number_in_row(grid, row, number) and
not number_in_col(grid, col, number) and
not number_in_box(grid, row, col, number)):
yield number
def main():
while True:
# Los ceros representan casilleros vacíos.
grid = [
[3, 0, 5, 6, 2, 9, 0, 0, 7],
[7, 0, 6, 1, 0, 8, 0, 0, 0],
[8, 0, 1, 0, 0, 0, 2, 6, 5],
[0, 0, 3, 0, 0, 5, 0, 7, 0],
[6, 8, 7, 0, 0, 0, 0, 0, 0],
[2, 0, 0, 7, 0, 0, 6, 0, 0],
[4, 7, 9, 5, 8, 0, 0, 2, 0],
[1, 0, 0, 4, 3, 0, 5, 0, 9],
[0, 0, 8, 9, 0, 0, 0, 0, 6],
]
s = \
"""\
+-----------------------+
| {} {} {} | {} {} {} | {} {} {} |
| {} {} {} | {} {} {} | {} {} {} |
| {} {} {} | {} {} {} | {} {} {} |
+-----------------------+
| {} {} {} | {} {} {} | {} {} {} |
| {} {} {} | {} {} {} | {} {} {} |
| {} {} {} | {} {} {} | {} {} {} |
+-----------------------+
| {} {} {} | {} {} {} | {} {} {} |
| {} {} {} | {} {} {} | {} {} {} |
| {} {} {} | {} {} {} | {} {} {} |
+-----------------------+
"""
while True:
possible_numbers = {
(row, col): None for row in range(9) for col in range(9)
}
# Obtener una lista de números posibles para cada una de
# las posiciones vacías.
for row in range(9):
for col in range(9):
number = grid[row][col]
if number == 0:
options = list(
get_possible_numbers(grid, row, col)
)
if options:
possible_numbers[(row, col)] = options
# Remover valores vacíos y ordenar por la cantidad de
# posibilidades.
possible_numbers = sorted(
(
(k, v)
for (k, v) in possible_numbers.items()
if v is not None
),
key=lambda kv: len(kv[1])
)
if possible_numbers:
# Obtener el primer item.
(row, col), numbers = possible_numbers[0]
# Fuerza bruta: obtener un número aleatorio de la
# lista de posibiilidades hasta que la grilla esté
# completa.
grid[row][col] = choice(numbers)
else:
break
# Chequear si la fuerza bruta dió resultado: si no hay más
# ceros en la grilla entonces el Sudoku está resuelto.
if 0 not in unpack(grid):
print(s.format(*(unpack(grid))))
break
if __name__ == "__main__":
main()
Explicación de solucionador de Sudoku
Bien, hagamos un análisis detallado de lo que realiza cada función y de como se ejecuta el script solucionador de sudoku.
- main() : en esta función se ejecuta el proceso principal del script, se ejecuta un ciclo while en el que se crea la celda de 9×9 que se quiere resolver. Dentro de este ciclo while se declara otro ciclo while en el que se itera a traves de cada casilla de la celda 9×9 y se estiman los posibles números que pueden aparecer en cada casilla. Luego se remueven los valores vacíos y se ordenan por la cantidad de valores posibles. Luego se itera de nuevo cada casilla y a traves de la fuerza bruta obtenemos un número aleatorio de la lista de valores posibles hasta que la celda este completa.
- number_in_row(grid, row, number) : esta función verifica que el número que le damos como argumento se encuentra en la fila especificada
- number_in_col(grid, col, number) : esta función verifica si el número que le damos como argumento se encuentra en la columna especificada
- number_in_box(grid, row, col, number) : aquí verificamos si el número indicado se encuentra en la subcelda 3×3 que corresponde a la posición especificada.
- reduce(n): pasamos de una posición en la celda 9×9 a una posición en una subcelda 3×3.
- box_by_pos(row, col) : función de utilidad que ayuda a number_in_box() a verificar si un número se encuentra en la subcelda de 3×3.
- get_possible_numbers(grid, row, col) : retorna los valores posibles para una casilla determinada.
Ejecutando solucionador de sudokus
Pasando la siguiente casilla:
grid = [
[3, 0, 5, 6, 2, 9, 0, 0, 7],
[7, 0, 6, 1, 0, 8, 0, 0, 0],
[8, 0, 1, 0, 0, 0, 2, 6, 5],
[0, 0, 3, 0, 0, 5, 0, 7, 0],
[6, 8, 7, 0, 0, 0, 0, 0, 0],
[2, 0, 0, 7, 0, 0, 6, 0, 0],
[4, 7, 9, 5, 8, 0, 0, 2, 0],
[1, 0, 0, 4, 3, 0, 5, 0, 9],
[0, 0, 8, 9, 0, 0, 0, 0, 6],
]
Nuestro script soluciona existosamente el sudoku:
+-----------------------+ | 3 4 5 | 6 2 9 | 8 1 7 | | 7 2 6 | 1 5 8 | 3 9 4 | | 8 9 1 | 3 7 4 | 2 6 5 | +-----------------------+ | 9 1 3 | 8 6 5 | 4 7 2 | | 6 8 7 | 2 4 3 | 9 5 1 | | 2 5 4 | 7 9 1 | 6 3 8 | +-----------------------+ | 4 7 9 | 5 8 6 | 1 2 3 | | 1 6 2 | 4 3 7 | 5 8 9 | | 5 3 8 | 9 1 2 | 7 4 6 | +-----------------------+
