Sudoku Solver
Un tablero de sudoku es una cuadrícula de 9 × 9 dividida en nueve recuadros de 3 × 3. En un tablero resuelto, cada fila, cada columna y cada recuadro contiene cada dígito del 1 al 9 exactamente una vez.
El rompecabezas se presenta como 9 cadenas, una por fila empezando desde arriba; un . es una celda vacía. Rellena todas las celdas vacías y devuelve el tablero resuelto en el mismo formato. El tablero tiene exactamente una solución.
Función
- boardstring-array
- las 9 filas del rompecabezas, un punto en cada celda vacía
- Devuelvestring-array
- las 9 filas del tablero resuelto
Restricciones
boardcontiene 9 cadenas de longitud 9.- Cada carácter es
.o uno de los dígitos1a9. - Los dígitos dados nunca se repiten dentro de una fila, una columna o una caja.
- El tablero tiene exactamente una solución.
Ejemplos
- Entrada
- board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
- Salida
- ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
- Explicación
- La fila superior
9.7.....6ya contiene 9, 7 y 6, así que sus seis casillas vacías llevan 1, 2, 3, 4, 5 y 8. Las columnas y los bloques determinan dónde va cada uno, y la fila queda957214386.
Para ir más allá
En un sudoku killer, las jaulas de celdas también deben sumar los valores indicados. ¿Cómo añadirías esa regla a la búsqueda y la usarías para descartar ramas antes?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Lleva un registro de los dígitos que ya contiene cada fila, cada columna y cada cuadro de 3 × 3. Así podrás determinar en O(1) si un dígito cabe en una celda vacía.
Rellena las celdas vacías de una en una. Prueba cada dígito que encaje en la celda, pasa a la siguiente celda y deshaz la colocación del dígito cuando no sea posible completar el resto del tablero con él.
El orden de las celdas importa. A continuación, completa la celda vacía a la que le queden menos dígitos: una celda con una opción no requiere ramificaciones, y una celda sin opciones te indica de inmediato que debes retroceder.
Solución
Resuélvelo mediante retroceso: coloca un dígito que encaje, continúa y deshazlo cuando no se pueda completar el tablero. El orden de las celdas determina la velocidad. En un tablero difícil, el orden de lectura puede recorrer cientos de millones de tableros parciales; rellenar primero la celda con menos opciones lleva alrededor de un centenar.
Retroceso en el orden de lectura
Correcto, pero no termina con las pruebas más grandes
Intuición
Rellena las celdas vacías en orden de lectura, cada una con el dígito más pequeño que encaje. Cuando a una celda no le queden dígitos, vuelve a la celda anterior y prueba con el siguiente. Se prueban por turnos todas las combinaciones que respetan las reglas, así que la búsqueda encuentra la solución.
Tres tablas hacen que cada prueba de encaje sea O(1): rowUsed[r][d], colUsed[c][d] y boxUsed[b][d], donde la caja b = (r / 3) * 3 + c / 3. Colocar un dígito establece tres entradas y quitarlo las borra.
El orden fijo es el punto débil: la búsqueda puede rellenar una fila entera con dígitos que encajan localmente y descubrir muchas celdas después que no dejan espacio. Un tablero cuyas filas superiores casi no tienen pistas, y cuyas soluciones son dígitos altos, hace que examine más de 300 millones de tableros parciales.
Algoritmo
- Lee el tablero en una cuadrícula con 0 para una celda vacía, completa
rowUsed,colUsedyboxUsed, y enumera las celdas vacías en orden de lectura. backtrack(k): sikes igual al número de celdas vacías, devuelve true.- Para cada dígito
ddel 1 al 9 que no se haya usado en la fila, columna y caja de la celdak, colócalo, márcalo y devuelve true sibacktrack(k+1)lo hace; de lo contrario, desmárcalo. - Si ningún dígito funciona, vacía la celda y devuelve false. Llama a
backtrack(0)y convierte la cuadrícula de nuevo en cadenas.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# row_used[r][d] is True when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
row_used = [[False] * 10 for _ in range(9)]
col_used = [[False] * 10 for _ in range(9)]
box_used = [[False] * 10 for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
else:
empties.append((r, c))
def backtrack(k):
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
grid[r][c] = d
row_used[r][d] = col_used[c][d] = box_used[b][d] = True
if backtrack(k + 1):
return True
row_used[r][d] = col_used[c][d] = box_used[b][d] = False
grid[r][c] = 0
return False
backtrack(0)
return ["".join(str(d) for d in row) for row in grid]Rellena primero la celda más vacía
Intuición
La solución no depende del orden de llenado, así que elige el orden que mantenga pequeña la búsqueda: en cada paso, llena la celda vacía que permita menos dígitos. Una celda con un solo dígito permitido es obligatoria y no agrega ninguna ramificación. Si una celda no permite ninguno, se elige de inmediato, así que un tablero incorrecto se detecta enseguida.
Para contar rápidamente los dígitos permitidos en las 81 celdas en cada paso, guarda cada fila, columna y bloque como una máscara de bits: el bit d de rows[r] está establecido cuando el dígito d está en la fila r. Una celda permite ~(rows[r] | cols[c] | boxes[b]) & 0x3FE, donde 0x3FE conserva los bits del 1 al 9, y la cantidad es el número de bits establecidos. Colocar d establece el bit d en tres máscaras; un OR exclusivo lo elimina.
Algoritmo
- Construye la cuadrícula y las máscaras
rows,colsyboxesa partir de los dígitos dados. backtrack(): recorre todas las celdas, calcula los dígitos permitidos para cada celda vacía y conserva la primera celda que tenga la menor cantidad. Si no hay ninguna celda vacía, return true.- Para cada dígito permitido de esa celda, colócalo, activa su bit en las tres máscaras y return true si
backtrack()lo hace; de lo contrario, desactiva los bits. - Si ningún dígito funciona, vacía la celda y return false. Llama a
backtrack()y vuelve a convertir la cuadrícula en cadenas.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# Bit d of rows[r] is set when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
rows[r] |= 1 << d
cols[c] |= 1 << d
boxes[(r // 3) * 3 + c // 3] |= 1 << d
def backtrack():
# Pick the empty cell with the fewest digits left (the first one on a tie).
best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
# Bits 1 to 9 of 0x3FE are the nine digits.
allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
count = bin(allowed).count("1")
if count < best_count:
best_r, best_c, best_allowed, best_count = r, c, allowed, count
if best_r == -1:
return True # no empty cell is left: the board is solved
r, c = best_r, best_c
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
bit = 1 << d
if best_allowed & bit:
grid[r][c] = d
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
if backtrack():
return True
rows[r] ^= bit
cols[c] ^= bit
boxes[b] ^= bit
grid[r][c] = 0
return False
backtrack()
return ["".join(str(d) for d in row) for row in grid]
Errores comunes y casos límite
- Olvidar borrar un dígito de los registros de fila, columna y bloque al deshacerlo. Más adelante, las celdas ven entonces el dígito como usado y la búsqueda no encuentra la solución.
- Usar
r / 3 + c / 3para el bloque. Las celdas(0, 4)y(4, 0)terminan ambas en 1, así que dos bloques comparten un mismo registro y el tablero nunca se puede completar. Usa(r / 3) * 3 + c / 3con división entera. - No detenerse en la primera solución. Los pasos para deshacer dejan entonces el tablero vacío de nuevo antes de que lo leas.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de un solucionador de sudoku mediante retroceso?
Exponencial en el peor caso, O(9^m) para m celdas vacías, porque cada celda puede ramificarse en hasta 9 dígitos. En los rompecabezas reales, las reglas de fila, columna y caja eliminan la mayoría de las ramas, y rellenar primero la celda más vacía elimina la mayoría de las restantes.
¿Cómo compruebas que un sudoku tiene exactamente una solución?
Ejecuta la misma búsqueda con retroceso, pero cuenta las soluciones y detente cuando el contador llegue a 2. Un contador de 1 significa que el rompecabezas tiene una solución única; 0 significa que no tiene solución. Los generadores de rompecabezas ejecutan esta comprobación después de eliminar cada pista.
¿Hay una forma más rápida de resolver sudoku que mediante backtracking?
La mayoría de quienes resuelven rápido siguen retrocediendo, pero deducen más cosas antes de cada conjetura. La propagación de restricciones completa cada celda que tiene una sola opción y cada dígito que encaja en una sola celda de su fila, columna o caja, y después repite el proceso. El Sudoku también puede plantearse como un problema de cobertura exacta y resolverse con el algoritmo X de Knuth.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def solveSudoku(board):
# Escribe el código aquíPrueba #1
Argumento
board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
Salida Esperada
["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]