Valid Sudoku

Q: ¿Cómo encuentras en qué cuadro de 3 × 3 está una celda?

Con la división entera, r / 3 es la franja de filas (0, 1 o 2) y c / 3 es el bloque de columnas. (r / 3) * 3 + c / 3 numera las cajas del 0 al 8, de izquierda a derecha y de arriba abajo. La celda (7, 1) está en la caja 2 * 3 + 0 = 6 , la de abajo a la izquierda.

MedioHashing

+10

Recibes un tablero de Sudoku de 9 × 9 como board, una lista de 9 cadenas con 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 la misma fila, la misma columna o el mismo cuadro de 3 × 3, y false en caso contrario. Solo se comprueban las celdas llenas: no es necesario que el tablero tenga solución.

Función

isValidSudoku(board: string-array) → boolean

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 ni caja de 3 × 3 repite un dígito; false en caso contrario

Restricciones

board.length == 9 y board[i].length == 9
board[i][j] es un dígito del 1 al 9 o .
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: Cada fila, columna y cuadro contiene cada dígito como máximo una vez. La fila 4 (contando desde 0), .74..89.3, tiene un 7, un 4, un 8, un 9 y un 3 una vez cada uno, y lo mismo ocurre con los otros 26 grupos, así que la respuesta es true.

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. Las dos celdas están en filas distintas y en cajas distintas; solo la comprobación de la columna detecta este caso.

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 5 de la fila 0, columna 8 y el 5 de la fila 2, columna 7 están en filas y columnas diferentes, pero ambos están en el cuadro superior derecho, así que la respuesta es false.

+16 pruebas ocultas al enviar

Para ir más allá

Generaliza la comprobación para un tablero de 16 × 16 con cajas de 4 × 4 y los símbolos del 1 al 9 y de la A a la G. ¿Qué números de tu código dependen del tamaño del tablero y en qué se convierte la fórmula de las cajas?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cada dígito pertenece a tres grupos a la vez: su fila, su columna y su caja de 3 × 3. Las filas y las columnas son directas de indexar; la caja es donde se producen la mayoría de los errores. Numera las cajas del 0 al 8 con (r / 3) * 3 + c / 3 y una sola pasada por las 81 celdas puede comprobar los 27 grupos a la vez.

Comprueba cada fila, columna y cuadro por separado

Intuición

Las reglas definen 27 grupos: 9 filas, 9 columnas y 9 cuadros. Reúne las nueve celdas de cada grupo y comprueba si se repite algún dígito entre ellas, ignorando los puntos. Si ningún grupo tiene repeticiones, el tablero es válido.

La fila i es board[i][0..8] y la columna i es board[0..8][i]. El cuadro i empieza en la fila 3 * (i / 3) y la columna 3 * (i % 3), usando división entera, así que el cuadro 5 empieza en la fila 3, columna 6. Su celda k está k / 3 filas hacia abajo y k % 3 columnas a la derecha de esa esquina.

Para encontrar una repetición entre nueve celdas, lleva un indicador de dígitos vistos y detente en el primer dígito que ya esté marcado. Cada una de las 81 celdas se lee tres veces, una por cada grupo al que pertenece: 243 lecturas, una cantidad fija de trabajo. En un tablero de n × n, el mismo método cuesta O(n²).

Algoritmo

Para i de 0 a 8, recopila la fila i, la columna i y la caja i, nueve celdas cada una.
La caja i empieza en top = 3 * (i / 3) y left = 3 * (i % 3); su celda k está en la fila top + k / 3, columna left + k % 3.
Para cada grupo, recorre sus celdas con indicadores «visto» 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 True

Una pasada con una tabla de elementos vistos por fila, columna y caja

Intuición

En lugar de recopilar grupos, visita cada celda una vez y haz las tres preguntas al mismo tiempo. 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 para las columnas y las cajas.

La celda (r, c) pertenece a la caja (r / 3) * 3 + c / 3. La primera parte selecciona la banda de tres cajas (las filas de 0 a 2 corresponden a la banda 0, las filas de 3 a 5 a la banda 1 y las filas de 6 a 8 a la banda 2), y c / 3 selecciona la caja dentro de la banda. La celda (4, 7) queda en la caja 1 * 3 + 2 = 5, la caja central de la derecha.

Para cada celda llena, si alguno de sus tres indicadores ya está activado, el dígito se repite en ese grupo y devuelves false de inmediato. De lo contrario, activas los tres. Cada celda se lee una vez y las tablas contienen 243 indicadores, así que el tiempo y la memoria son fijos para un tablero de 9 × 9, y O(n²) para uno de n × n.

Algoritmo

Crea seenRow, seenCol y seenBox, cada uno de 9 × 9 y todos con valor false.
Recorre cada celda (r, c); omítela si contiene un punto.
Sea d el dígito menos 1 y b = (r / 3) * 3 + c / 3.
Si seenRow[r][d], seenCol[c][d] o seenBox[b][d] es true, devuelve false.
De lo contrario, establece los tres en true. 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

Las comprobaciones de filas y columnas rara vez fallan. Los errores están en el índice de la caja y en qué se considera una repetición.

Calcular la caja como r / 3 + c / 3. Eso solo da valores de 0 a 4, así que las celdas (0, 3) y (3, 0) comparten un número aunque estén en cajas diferentes, y dos 7 en ellas se consideran una repetición. Usa (r / 3) * 3 + c / 3.
Dividir con / en JavaScript, Python 3 o Lua, donde 4 / 3 es 1.33, no un número de caja. Usa Math.floor, // o math.floor.
Tratar . como un valor. Un tablero vacío tiene nueve puntos en cada fila, y es válido.
Intentar resolver el rompecabezas. Con 12345678. como fila 0 y un 9 más abajo en la columna 8, la última celda de la fila 0 nunca puede completarse; sin embargo, ningún grupo repite un dígito, así que la respuesta es true.
Comprobar las filas y las columnas, pero no las cajas. Una cuadrícula completa en la que cada fila es la anterior desplazada un lugar a la izquierda no tiene repeticiones en ninguna fila ni columna, mientras que cada caja contiene repeticiones.

Preguntas frecuentes4

¿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 memoria O(1). 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, así que requiere O(n²) de tiempo y memoria.

¿Tiene que ser resoluble un tablero de Sudoku válido?

No. Aquí, válido significa únicamente que ningún dígito se repite en una fila, una columna o un bloque de 3 × 3 entre las celdas que ya están llenas. Un tablero puede superar esa comprobación y aun así no tener solución. Para determinar si tiene solución, se necesita una búsqueda como el retroceso, que es un problema distinto.

¿Cómo encuentras en qué cuadro de 3 × 3 está una celda?

Con la división entera, r / 3 es la franja de filas (0, 1 o 2) y c / 3 es el bloque de columnas. (r / 3) * 3 + c / 3 numera las cajas del 0 al 8, de izquierda a derecha y de arriba abajo. La celda (7, 1) está en la caja 2 * 3 + 0 = 6, la de abajo a la izquierda.

¿Se puede resolver un Sudoku válido con máscaras de bits?

Sí. Asigna un entero a cada fila, columna y bloque, y haz que el bit d indique que se ha visto el dígito d+1. Para una celda llena, calcula 1 << d; si al hacer AND con cualquiera de las tres máscaras el resultado es distinto de cero, el dígito se repite; de lo contrario, haz OR con ese valor en las tres. Son 27 enteros en lugar de 243 indicadores, con la misma lógica de una sola pasada.

Python

def isValidSudoku(board):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]

Esperado

true