Sudoku válido (LeetCode 36): solución en Python, índice de caja y casos límite

Sudoku válido (LeetCode 36) te da un tablero de 9 por 9 parcialmente lleno y te pregunta si las celdas llenas infringen alguna regla del sudoku. No tienes que resolver el puzzle. Solo verificas que ningún dígito se repita en una fila, una columna o un recuadro de 3 por 3. Una sola pasada con tres conjuntos de dígitos vistos lo resuelve en O(81), que es constante.

El problema

El tablero es una cuadrícula de 9 por 9 de caracteres, cada uno un dígito del 1 al 9 o . para vacío. Devuelve true si las celdas llenas cumplen estas reglas:

• Cada fila no tiene dígitos repetidos.
• Cada columna no tiene dígitos repetidos.
• Cada recuadro de 3 por 3 no tiene dígitos repetidos.

Un tablero puede ser válido aunque no tenga solución. Solo se verifican las celdas llenas.

Enfoque: tres conjuntos por unidad

Mantén un conjunto de dígitos vistos para cada fila, cada columna y cada recuadro. Para cada celda llena, revisa el dígito en los tres conjuntos y agrégalo si es nuevo.

La única parte que requiere pensar es el índice del recuadro. Para una celda en la fila r y la columna c, el número de recuadro es (r // 3) * 3 + c // 3. Cuenta los recuadros de izquierda a derecha y de arriba hacia abajo, del 0 al 8.

def is_valid_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == ".":
                continue
            b = (r // 3) * 3 + c // 3
            if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
                return False
            rows[r].add(ch)
            cols[c].add(ch)
            boxes[b].add(ch)
    return True

Traza

Supón que la fila 0 tiene 5 en la columna 0 y otro 5 en la columna 4. El primer 5 se agrega a rows[0], cols[0] y boxes[0]. En la columna 4, la comprobación ch in rows[0] es verdadera, así que la función devuelve false de inmediato. Los dígitos iguales en el mismo recuadro o columna se detectan de la misma forma con los otros dos conjuntos.

Complejidad

El tablero siempre es de 9 por 9, así que el tiempo es constante, 81 visitas a celdas. Si lo generalizas a un tablero de n por n, es O(n al cuadrado) en tiempo y O(n al cuadrado) en espacio. Menciona ambos, porque en las entrevistas suelen preguntar cómo escala.

Variaciones que piden en las entrevistas

La versión con bitmask reemplaza cada conjunto por un entero. mask & (1 << d) prueba un dígito y mask |= 1 << d lo registra. Es más rápida, pero la versión con conjuntos es más fácil de escribir bien bajo presión, así que escribe esa primero.

Errores comunes

• Revisar filas y columnas pero olvidar los recuadros.
• Una fórmula de recuadro incorrecta, como r // 3 + c // 3, que da el mismo índice a recuadros distintos.
• Tratar . como un dígito, de modo que dos celdas vacías cuentan como una repetición.
• Intentar resolver el tablero cuando la pregunta solo pide validez.

Casos límite para probar

Cómo explicarlo en una entrevista

1. Repite las reglas y aclara que solo validas, no resuelves.
2. Nombra las tres unidades y di que cada una necesita un conjunto de vistos.
3. Da la fórmula del índice del recuadro y explícala con un ejemplo.
4. Escribe la pasada única y el retorno anticipado.
5. Indica la complejidad y ofrece la versión con bitmask si te lo piden.

Probé el código de arriba contra una verificación simple de fila, columna y recuadro en 20.000 tableros aleatorios, algunos válidos y otros rotos a propósito, antes de publicarlo. Una verificación aleatoria rápida como esa es un buen hábito cuando practicas.

Práctica relacionada

Consulta nuestra chuleta de Big O para los términos de complejidad, la lista LeetCode Blind 75 para saber qué practicar después, y la guía del asistente para entrevistas de programación para saber cómo practicar.

Explica tu enfoque en voz alta mientras programas. Una transcripción muestra si enunciaste la observación clave antes de escribir. Sigue las reglas del empleador sobre herramientas de IA en cualquier evaluación en vivo.