Resolución de sudokus en Python
El sudoku es un juego de lógica que consiste en rellenar una cuadrícula de 9 x 9 con los números del 1 al 9, de forma que cada número aparezca una sola vez en cada fila, columna y cuadrado de 3 x 3.
En este tutorial, veremos cómo resolver sudokus en Python utilizando el algoritmo de backtracking. El backtracking es un algoritmo recursivo que consiste en probar todas las posibles soluciones a un problema, descartando aquellas que no sean válidas.
Prerrequisitos
Para seguir este tutorial, es necesario tener conocimientos básicos de programación en Python. Además, es recomendable tener instalado el paquete numpy, que nos permitirá trabajar con matrices de forma sencilla.
Implementación
El algoritmo de backtracking para resolver sudokus se puede dividir en los siguientes pasos:
- Inicializar la cuadrícula
En primer lugar, debemos inicializar la cuadrícula con los números que ya están dados.
def init_grid(grid):
"""
Inicializa la cuadrícula con los números que ya están dados.
Args:
grid: La cuadrícula de sudoku.
Returns:
La cuadrícula inicializada.
"""
for row, row_data in enumerate(grid):
for col, col_data in enumerate(row_data):
if col_data != 0:
grid[row][col] = col_data
return grid
- Buscar una casilla vacía
Una vez inicializada la cuadrícula, debemos buscar una casilla vacía para empezar a resolver el sudoku.
def find_empty_cell(grid):
"""
Busca una casilla vacía en la cuadrícula.
Args:
grid: La cuadrícula de sudoku.
Returns:
La posición de la casilla vacía, o None si no hay ninguna.
"""
for row in range(9):
for col in range(9):
if grid[row][col] == 0:
return row, col
return None
- Probar todos los posibles números
Una vez encontrada una casilla vacía, debemos probar todos los posibles números para esa casilla.
def solve_sudoku(grid):
"""
Resuelve el sudoku.
Args:
grid: La cuadrícula de sudoku.
Returns:
True si el sudoku tiene solución, False si no.
"""
row, col = find_empty_cell(grid)
if row is None:
return True
for number in range(1, 10):
if is_valid_number(grid, row, col, number):
grid[row][col] = number
if solve_sudoku(grid):
return True
grid[row][col] = 0
return False
- Comprobar la validez de un número
Para comprobar que un número es válido para una casilla, debemos comprobar que no se repite en la fila, columna o cuadrado de 3 x 3 en el que se encuentra.
def is_valid_number(grid, row, col, number):
"""
Comprueba si un número es válido para una casilla.
Args:
grid: La cuadrícula de sudoku.
row: La fila de la casilla.
col: La columna de la casilla.
number: El número a comprobar.
Returns:
True si el número es válido, False si no.
"""
# Comprobar la fila
for col in range(9):
if grid[row][col] == number:
return False
# Comprobar la columna
for row in range(9):
if grid[row][col] == number:
return False
# Comprobar el cuadrado
row_start = (row // 3) * 3
col_start = (col // 3) * 3
for row in range(row_start, row_start + 3):
for col in range(col_start, col_start + 3):
if grid[row][col] == number:
return False
return True
