Valid Sudoku
Recibes un tablero de Sudoku de 9 × 9 como board, una lista de 9 cadenas de 9 caracteres cada una, una cadena por fila. Cada carácter es un dígito del 1 al 9 o . para una celda vacía. Devuelve true si ningún dígito aparece dos veces en una fila, una columna o un bloque de 3 × 3, y false en caso contrario. Solo se comprueban las celdas llenas: el tablero no tiene que tener solución.
Función
- boardstring-array
- 9 cadenas de 9 caracteres, una por fila, dígitos del 1 al 9 y . para una celda vacía
- Devuelveboolean
- true si ninguna fila, columna o cuadro de 3 × 3 repite un dígito; false en caso contrario
Restricciones
board.length == 9yboard[i].length == 9board[i][j]es un dígito del1al9o.- Puede que sea imposible completar el tablero; solo importan las repeticiones entre las celdas rellenadas.
Ejemplos
- Entrada
- board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
- Salida
- true
- Explicación
- La fila 4, contando desde 0,
.74..89.3, contiene 7, 4, 8, 9 y 3 una vez cada uno, y ninguno de los otros 26 grupos repite un dígito tampoco.
- Entrada
- board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
- Salida
- false
- Explicación
- La fila 0 y la fila 7 empiezan ambas con un
3, así que la columna 0 contiene dos 3. No comparten fila ni bloque, así que solo la comprobación de la columna lo detecta.
- Entrada
- board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
- Salida
- false
- Explicación
- El
5de la fila 0, columna 8 y el5de la fila 2, columna 7 no comparten fila ni columna, pero ambos están en el cuadro superior derecho, así que la respuesta esfalse.
Para ir más allá
¿Cómo comprobarías un tablero de 16 × 16 con bloques de 4 × 4 y los símbolos del 1 al 9 y de la A a la G? ¿En qué se convierte la fórmula del bloque?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Enumera los grupos de los que hablan las reglas. ¿Cuántos hay y qué tipo es el más difícil de indexar?
La celda de la fila
ry la columnacse encuentra en exactamente una caja. Con la división entera,r / 3indica en qué banda de tres filas está yc / 3en qué bloque de tres columnas. Combina ambos en un solo número del 0 al 8.Visita cada celda una vez. Mantén una marca de «visto» para cada par (fila, dígito), (columna, dígito) y (cuadro, dígito). Una celda llena cuya marca ya esté activada en cualquiera de sus tres grupos es una repetición.
Solución
Cada dígito pertenece a tres grupos: su fila, su columna y su caja de 3 × 3. Las filas y las columnas se indexan directamente; en la caja es donde viven los errores. Numera las cajas del 0 al 8 con (r / 3) * 3 + c / 3, y una pasada por las 81 celdas comprueba los 27 grupos.
Comprueba cada fila, columna y cuadro por separado
Intuición
La regla nombra 27 grupos: 9 filas, 9 columnas y 9 cajas. Reúne las nueve celdas de cada grupo y busca un dígito repetido, ignorando los puntos. El tablero es válido exactamente cuando ningún grupo tiene uno.
Una marca de visto por dígito detecta una repetición entre nueve celdas. Cada una de las 81 celdas se lee una vez por cada uno de sus tres grupos: 243 lecturas, una cantidad fija de trabajo. En un tablero de n × n, el mismo método cuesta O(n²).
Algoritmo
- Para
idesde 0 hasta 8, recopila la filai, la columnaiy la cajai. - La caja
itiene su esquina en la fila3 * (i / 3), la columna3 * (i % 3); su celdakesták / 3filas hacia abajo yk % 3columnas a la derecha. - Recorre cada grupo con indicadores de elementos vistos nuevos, omitiendo los puntos. Si un dígito ya está marcado, devuelve
false. - Después de los 27 grupos, devuelve
true.
def has_repeat(cells):
seen = set()
for ch in cells:
if ch == '.':
continue
if ch in seen:
return True
seen.add(ch)
return False
def isValidSudoku(board):
for r in range(9):
if has_repeat(board[r][c] for c in range(9)):
return False
for c in range(9):
if has_repeat(board[r][c] for r in range(9)):
return False
for top in (0, 3, 6):
for left in (0, 3, 6):
box = (board[top + i][left + j] for i in range(3) for j in range(3))
if has_repeat(box):
return False
return TrueUna pasada con una tabla de elementos vistos por fila, columna y bloque
Intuición
Visita cada celda una vez y haz las tres preguntas a la vez. Mantén tres tablas de indicadores de 9 × 9: seenRow[r][d] indica que el dígito d+1 ya está en la fila r, y seenCol y seenBox funcionan de la misma manera.
La celda (r, c) pertenece a la caja (r / 3) * 3 + c / 3. La primera parte selecciona la franja de tres cajas, y c / 3 selecciona la caja dentro de la franja. La celda (4, 7) cae en la caja 1 * 3 + 2 = 5, la caja central derecha.
Un indicador que ya está activado significa que el dígito se repite en ese grupo. Cada celda se lee una vez y las tablas contienen 243 indicadores: tiempo y memoria constantes en este caso, O(n²) en un tablero de n × n.
Algoritmo
- Crea
seenRow,seenColyseenBox, cada uno de 9 × 9 y todo en false. - Para cada celda llena
(r, c), seadsu dígito menos 1 yb = (r / 3) * 3 + c / 3. - Si
seenRow[r][d],seenCol[c][d]oseenBox[b][d]está establecido, devuelvefalse; de lo contrario, establece los tres. - Después de la última celda, devuelve
true.
def isValidSudoku(board):
# seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
seen_row = [[False] * 9 for _ in range(9)]
seen_col = [[False] * 9 for _ in range(9)]
seen_box = [[False] * 9 for _ in range(9)]
for r in range(9):
for c in range(9):
ch = board[r][c]
if ch == '.':
continue
d = int(ch) - 1
b = (r // 3) * 3 + c // 3
if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
return False
seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
return True
Errores comunes y casos límite
- Calcular la caja como
r / 3 + c / 3. Solo da valores del 0 al 4, así que(0, 3)y(3, 0)comparten un número aunque sus cajas sean distintas, y dos 7 en ellas se reportan como una repetición. - Dividir con
/en JavaScript, Python 3 o Lua, donde4 / 3es1.33. Redondea hacia abajo. - Tratar
.como un valor. Un tablero vacío, con nueve puntos por fila, es válido. - Intentar resolver el rompecabezas. Una fila 0 de
12345678.con un 9 más abajo en la columna 8 nunca se puede completar y, aun así, nada se repite:true. - Omitir las cajas. En una cuadrícula completa donde cada fila es la anterior desplazada un lugar a la izquierda, no hay repeticiones en ninguna fila ni columna, mientras que todas las cajas contienen repeticiones.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Valid Sudoku?
El tablero siempre tiene 81 celdas, así que ambos enfoques se ejecutan en tiempo O(1) y usan O(1) de memoria. Para un Sudoku general de n × n, la comprobación de una pasada lee cada una de las n² celdas una vez y mantiene 3n² indicadores: tiempo y memoria O(n²).
¿Un tablero de Sudoku válido tiene que tener solución?
No. Válido aquí significa únicamente que ningún dígito se repite en una fila, una columna o una caja de 3 × 3 entre las celdas rellenadas. Un tablero puede superar esa comprobación y aun así no tener solución. Determinar si tiene solución requiere una búsqueda como el retroceso, que es un problema distinto.
¿Se puede resolver un Sudoku válido con máscaras de bits?
Sí. Asigna un entero a cada fila, columna y caja, donde el bit d significa que se ha visto el dígito d+1. Para una celda llena, si 1 << d al hacer AND con cualquiera de sus tres máscaras da un valor distinto de cero, el dígito se repite; de lo contrario, haz OR con él en las tres. Son 27 enteros en lugar de 243 indicadores.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def isValidSudoku(board):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Salida Esperada
true