Resolviendo un Sudoku con Python
El otro día estaba haciendo un Sudoku con lápiz y papel, cuando se me ocurrió pensar: “Si fuera un ordenador terminaría esto en un momento”. Y después: “Pero si para eso se inventó el Python”. En el improbable caso de que no sepas cómo funciona un Sudoku puedes leer una explicación estupenda en la Wikipedia.
Aquí puedes descargar el programa analizador de Sudokus, ¡en poco más de 200 líneas!
El método es muy sencillo. Por cada casilla del tablero se mantiene una lista de números posibles. Si una casilla solo tiene un número, entonces se borra éste de las demás casillas de la fila, columna y sector. Al borrar números es posible que alguna lista pase a tener una sola opcion, en cuyo caso se repite la operación. El programa termina cuando todas las casillas tienen un único número o cuando se encuentra una lista sin ningún número posible, en cuyo caso no hay solución.
Si se llega a un punto muerto, en el que no se pueda seguir borrando números, pero no se haya terminado, entonces hay que adivinar. Primero se busca la casilla con menos opciones, se hace una copia del tablero entero, nos quedamos con el primer número, y se sigue borrando números normalmente. Si se llega a una solución, hecho, si no, volvemos a la copia, pasamos a la suposición siguiente y repetimos. Si acabamos la lista de opciones entonces no hay solución.
Este paso de suposiciones se repite recursivamente tantas veces como sea necesario.
El código
Lo primero son los nombres globales del programa:
GRID_SIZE = 9 SUBGRID_SIZE = 3 RANGE_ROW = range(GRID_SIZE) g_exclusion = []
Las dos primeras se pueden cambiar para hacer Sudokus no estándar. La tercera es una lista constante, de 0 a 8, para optimizar los bucles.
g_exclusion se inicializa en la función InitGlobals(), y es una lista de listas de listas de pares (¡uf!), de tal manera que g_exclusion[y][x] es una lista de las coordenadas de las casillas con cuyo número no puede coincidir.
Por ejemplo, g_exclusion[1][2] es igual a [(1, 0), (0, 2), (1, 1), (2, 2), (1, 3), (3, 2), (1, 4), (4, 2), (1, 5), (5, 2), (1, 6), (6, 2), (1, 7), (7, 2), (1, 8), (8, 2), (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2)], que son la fila 1, la columna 2, y el sector superior izquierdo, excepto la propia casilla (1,2).
Esta lista se construye inicialmente como optimización, para no tener que calcularla cada vez que se necesita.
El resto del trabajo lo hace la clase Sudoku, que se construye pasando como parámetro la descripción de la posición inicial en una lista de strings, uno por cada línea, y un número o blanco por casilla. Por ejemplo, el Sudoku de la Wikipedia es:
53 7
6 195
98 6
8 6 3
4 8 3 1
7 2 6
6 28
419 5
8 79
La clase Sudoku contiene un miembro llamado grid, que es una lista de listas de listas, de forma que grid[y][x] es la lista de números posibles en la posición (y,x). Esta lista se construye con la función auxiliar:
def InitCell(v): if v==0: return range(1,GRID_SIZE+1) else: return [v]
La función Sudoku.DoGaps() recorre el tablero grid buscando listas de longitud 1 (números fijos), y para cada una de ellas recorre la lista de g_exclusion correspondiente borrando el número fijo de la casilla inicial. Devuelve True si se ha hecho algún cambio o False si no se hace nada.
class Sudoku: #... def DoGaps(self, indent): changed = False; for y in RANGE_ROW: for x in RANGE_ROW: c = self.Grid(y,x) if len(c) != 1: continue v = c[0] for e in g_exclusion[y][x]: n = self.Grid(*e) if v in n: changed = True n.remove(v) return changed
La función Sudoku.FindBest() recorre el tablero buscando la lista más corta de números, que no sea de longitud 1. Si encuentra alguna lista vacía devuelve False inmediatamente. Si todas las listas son de longitud 1, el Sudoku está completo y devuelve True. En otro caso devuelve un par con las coordenadas de la casilla más corta. Hacer que una función devuelva un booleano o una tupla, según la situación, quizás no sea mi idea más brillante… pero ¡eh! es Python, puede hacerse, y las alternativas no me convencen 
.
class Sudoku: #... def FindBest(self): best = None bestlen = 1000 # a (relative) big number for y in RANGE_ROW: for x in RANGE_ROW: c = self.Grid(y,x) n = len(c) if n==0: return False #Impossible elif n == 1: continue elif n < bestlen: bestlen = len(c) best = (y,x) if not best: return True #Success return best
Finalmente, la función Sudoku.Solve() enlaza las demás funciones y hace todo el trabajo. Primero llama a DoGaps() hasta que devuelva False. Luego llama a FindBest() y comprueba si termina con éxito o fracaso, devolviendo True o False, respectivamente, o si tiene que intentar adivinar. En este último caso hacemos un bucle sobre las posibles soluciones de esta casilla, y para cada una hacemos una copia de grid, fijamos la casilla que estamos suponiendo y llamamos a Solve() recursivamente. Si esta última devuelve True terminamos con éxito, si no, pasamos a la siguiente. Y si se agotan todas devolvemos False indicando que no hay solución.
class Sudoku: #... def Solve(self): while self.DoGaps(indent): pass best = self.FindBest() if best==True: return True if best==False: return False y,x = best backupGrid = self.grid for guess in backupGrid[y][x]: self.grid = copy.deepcopy(backupGrid) self.grid[y][x] = InitCell(guess) if self.Solve(): return True return False
Nótese que la copia de grid se debe hacer con la función copy.deepcopy().
Opciones
Este programa interpreta las siguientes opciones:
- -a, –all: No se para cuando encuentra una solución, sigue buscando por si encuentra más.
- -v, –verbose: Explica qué hace y cómo va colocando los números. Sirve para hacer creer a la gente que lo has resuelto tú a mano.
- –moreverbose: Escribe en el terminal todo lo que hace (útil para depurar).
Puedes descargar el programa aquí.
Artículos relacionados:
- C++, GDB y Python Descarga el fichero aquí. Hace unos días, construyendo una versión...
- Comparación entre booleanos Quiero protestar desde aquí contra la costumbre, bastante extendida, de...
RSS
Deja un comentario