Sudoku Valido (LeetCode 36): Soluzione Python, Indice del Riquadro e Casi Limite

Il Sudoku Valido (LeetCode 36) ti fornisce una griglia 9x9 parzialmente riempita e ti chiede se le celle riempite violano qualche regola del sudoku. Non devi risolvere il puzzle. Devi solo verificare che nessuna cifra si ripeta in una riga, in una colonna o in un riquadro 3x3. Una sola passata con tre insiemi di cifre viste basta, in O(81), che è costante.

Il problema

La griglia è una matrice 9x9 di caratteri, ognuno una cifra da 1 a 9 oppure . per le celle vuote. Restituisci true se le celle riempite rispettano queste regole:

• Ogni riga non ha cifre ripetute.
• Ogni colonna non ha cifre ripetute.
• Ogni riquadro 3x3 non ha cifre ripetute.

Una griglia può essere valida anche se non ha soluzione. Si controllano solo le celle riempite.

Approccio: tre insiemi per unità

Mantieni un insieme di cifre viste per ogni riga, ogni colonna e ogni riquadro. Per ogni cella riempita, controlla la cifra in tutti e tre gli insiemi e aggiungila se è nuova.

L'unica parte che richiede un po' di ragionamento è l'indice del riquadro. Per una cella alla riga r e colonna c, il numero del riquadro è (r // 3) * 3 + c // 3. Conta i riquadri da sinistra a destra, dall'alto verso il basso, da 0 a 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

Traccia

Supponi che la riga 0 abbia 5 alla colonna 0 e un altro 5 alla colonna 4. Il primo 5 viene aggiunto a rows[0], cols[0] e boxes[0]. Alla colonna 4, il controllo ch in rows[0] è vero, quindi la funzione restituisce subito false. Cifre uguali nello stesso riquadro o nella stessa colonna vengono intercettate allo stesso modo dagli altri due insiemi.

Complessità

La griglia è sempre 9x9, quindi il tempo è costante, 81 visite di celle. Se generalizzi a una griglia n x n, è O(n al quadrato) come tempo e O(n al quadrato) come spazio. Dì entrambe le cose, perché i colloqui spesso chiedono come scala.

Varianti che i colloqui chiedono

La versione con bitmask sostituisce ogni insieme con un intero. mask & (1 << d) verifica una cifra e mask |= 1 << d la registra. È più veloce, ma la versione con gli insiemi è più facile da scrivere correttamente sotto pressione, quindi scrivi prima quella.

Errori comuni

• Controllare righe e colonne ma dimenticare i riquadri.
• Una formula sbagliata per il riquadro, come r // 3 + c // 3, che assegna lo stesso indice a riquadri diversi.
• Trattare . come una cifra, così due celle vuote contano come ripetizione.
• Cercare di risolvere la griglia quando la domanda chiede solo se è valida.

Casi limite da testare

Come spiegarlo in un colloquio

1. Ripeti le regole e dì che devi solo validare, non risolvere.
2. Nomina le tre unità e dì che ognuna richiede un insieme di cifre viste.
3. Fornisci la formula dell'indice del riquadro e spiegana con un esempio.
4. Scrivi la passata singola e il ritorno anticipato.
5. Dichiara la complessità e proponi la versione con bitmask se te la chiedono.

Ho testato il codice qui sopra contro un semplice controllo di riga, colonna e riquadro su 20.000 griglie casuali, alcune valide e altre volutamente rotte, prima di pubblicare. Un rapido controllo casuale come questo è una buona abitudine quando ti eserciti.

Esercizi correlati

Consulta il nostro cheat sheet sulla Big O per i termini di complessità, la lista LeetCode Blind 75 per cosa esercitare dopo, e la guida all'assistente per colloqui di programmazione per come esercitarti.

Ragiona ad alta voce mentre scrivi il codice. Una trascrizione mostra se hai enunciato l'osservazione chiave prima di scrivere. Segui le regole del datore di lavoro sugli strumenti di IA in qualsiasi valutazione dal vivo.