También se puede hacer que el ordenador resuelva un sudoku. Lo más sencillo es probar números en las casillas vacías y, si te atascas, volver un paso atrás y reintentar. Este método se llama backtracking (vuelta atrás).
La idea del backtracking
- Busca la primera casilla vacía, empezando por arriba a la izquierda.
- Prueba a poner en ella del 1 al 9, por orden. Si ya hay ese número en la misma fila, columna o caja, sáltalo.
- Si cabe algún número, ponlo y pasa a la siguiente casilla vacía.
- Si llegas a una casilla donde no cabe ningún número, vuelve a la casilla anterior y prueba el siguiente número.
- Cuando ya no queden casillas vacías, el sudoku está resuelto.
Una persona evita adivinar, pero el ordenador puede volver atrás enseguida si se equivoca, así que probando a lo bruto llega pronto a la solución.
En Python
El tablero se representa como una lista de 81 números, de izquierda a derecha y de arriba abajo (0 es una casilla vacía). En la casilla número i, el cociente de i÷9 es la fila y el resto es la columna.
def can_place(grid, r, c, d):
# se puede poner d si no está en la misma fila, columna o caja
for k in range(9):
if grid[r * 9 + k] == d or grid[k * 9 + c] == d:
return False
br, bc = r // 3 * 3, c // 3 * 3
for rr in range(br, br + 3):
for cc in range(bc, bc + 3):
if grid[rr * 9 + cc] == d:
return False
return True
def solve(grid):
# busca una casilla vacía y prueba del 1 al 9; si te atascas, vuelve atrás
for i in range(81):
if grid[i] == 0:
r, c = divmod(i, 9)
for d in range(1, 10):
if can_place(grid, r, c, d):
grid[i] = d
if solve(grid):
return True
grid[i] = 0
return False
return True
puzzle = "3..5..182.....2.9.8.2.91.4...52.9..6724.1.8396..4.85...5.12.9.7.3.7.....267..4..8"
grid = [0 if ch == "." else int(ch) for ch in puzzle]
solve(grid)
for r in range(9):
print(" ".join(str(v) for v in grid[r * 9 : r * 9 + 9])) Al ejecutarlo, se muestra la solución así. El problema es uno de ★1 de la app NumberPlace.
3 4 9 5 6 7 1 8 2
5 1 6 8 4 2 7 9 3
8 7 2 3 9 1 6 4 5
1 8 5 2 3 9 4 7 6
7 2 4 6 1 5 8 3 9
6 9 3 4 7 8 5 2 1
4 5 8 1 2 3 9 6 7
9 3 1 7 8 6 2 5 4
2 6 7 9 5 4 3 1 8 Contar cuántas soluciones hay
Al crear problemas, quieres comprobar que la solución es única (por qué un sudoku tiene una sola solución). Si cambias un poco el programa anterior para que no pare al encontrar una solución, sino que siga contando, sabrás cuántas hay. En cuanto encuentra dos ya sabe que no es única, así que se detiene ahí.
def count_solutions(grid, limit=2):
# se detiene al encontrar limit soluciones (con 2 ya se sabe que no es única)
for i in range(81):
if grid[i] == 0:
r, c = divmod(i, 9)
found = 0
for d in range(1, 10):
if can_place(grid, r, c, d):
grid[i] = d
found += count_solutions(grid, limit - found)
grid[i] = 0
if found >= limit:
break
return found
return 1
grid = [0 if ch == "." else int(ch) for ch in puzzle]
print(count_solutions(grid)) Con el problema de ★1 de arriba se muestra 1, y con un problema que tenga dos soluciones se muestra 2.
Trucos para ir más rápido
En vez de probar de arriba a la izquierda en orden, si pruebas empezando por la casilla donde caben menos números, todo va mucho más rápido. Si empiezas por las casillas con un solo candidato, casi no hace falta volver atrás. Cuando NumberPlace comprueba el número de soluciones, también prueba en este orden.
Resolver con las mismas técnicas que una persona
El backtracking es rápido y seguro, pero no te dice «por qué va ahí ese número». Para la «Pista» de NumberPlace y para valorar la dificultad de los problemas se usa otro método.
- Guardar, para cada casilla vacía, los números que caben (los candidatos).
- Buscar, empezando por las técnicas más fáciles, la que se pueda aplicar.
- Tras dar un paso, volver a buscar desde la técnica más fácil.
Las técnicas son 15, ordenadas de más fácil a más difícil: desde «solo cabe aquí» y «solo cabe este número», pasando por los candidatos bloqueados y las parejas, hasta X-Wing, XY-Wing y Swordfish (cómo resolver un sudoku). Como se avanza en el mismo orden que una persona, se sabe qué técnica hizo falta; con eso se decide la ★ y la Pista puede explicar el motivo.
