Geldige Sudoku (LeetCode 36): Python-oplossing, boxindex en edge cases

Geldig Sudoku (LeetCode 36) geeft je een deels ingevuld bord van 9 bij 9 en vraagt of de ingevulde cellen een sudokuregel overtreden. Je hoeft de puzzel niet op te lossen. Je controleert alleen dat geen enkel cijfer herhaald wordt in een rij, een kolom of een blok van 3 bij 3. Eén pass met drie sets van geziene cijfers doet het in O(81), wat constant is.

Het probleem

Het bord is een raster van 9 bij 9 met tekens, elk een cijfer van 1 tot 9 of . voor leeg. Geef true terug als de ingevulde cellen deze regels volgen:

• Elke rij heeft geen herhaald cijfer.
• Elke kolom heeft geen herhaald cijfer.
• Elk blok van 3 bij 3 heeft geen herhaald cijfer.

Een bord kan geldig zijn zelfs als het geen oplossing heeft. Alleen de ingevulde cellen worden gecontroleerd.

Aanpak: drie sets per eenheid

Houd een set bij van geziene cijfers voor elke rij, elke kolom en elk blok. Controleer voor elke ingevulde cel het cijfer in alle drie de sets, en voeg het toe als het nieuw is.

Het enige deel dat denkwerk kost, is de blokindex. Voor een cel op rij r en kolom c is het bloknummer (r // 3) * 3 + c // 3. Het telt blokken van links naar rechts, van boven naar beneden, van 0 tot 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

Trace

Stel dat rij 0 een 5 heeft op kolom 0 en nog een 5 op kolom 4. De eerste 5 wordt toegevoegd aan rows[0], cols[0] en boxes[0]. Bij kolom 4 is de controle ch in rows[0] waar, dus de functie geeft meteen false terug. Gelijke cijfers in hetzelfde blok of dezelfde kolom worden op dezelfde manier door de andere twee sets opgemerkt.

Complexiteit

Het bord is altijd 9 bij 9, dus de tijd is constant, 81 celbezoeken. Als je generaliseert naar een bord van n bij n, is het O(n kwadraat) tijd en O(n kwadraat) ruimte. Noem beide, want interviewers vragen vaak hoe het schaalt.

Varianten die interviewers vragen

De bitmask-versie vervangt elke set door een integer. mask & (1 << d) test een cijfer en mask |= 1 << d registreert het. Het is sneller, maar de set-versie is makkelijker om goed te krijgen onder tijdsdruk, dus schrijf die eerst.

Veelgemaakte fouten

• Rijen en kolommen controleren maar de blokken vergeten.
• Een verkeerde blokformule, zoals r // 3 + c // 3, waardoor verschillende blokken dezelfde index krijgen.
• . als een cijfer behandelen, waardoor twee lege cellen als een herhaling tellen.
• Het bord proberen op te lossen terwijl de vraag alleen om geldigheid vraagt.

Randgevallen om te testen

Hoe je het uitlegt in een interview

1. Herhaal de regels en zeg dat je alleen valideert, niet oplost.
2. Noem de drie eenheden en zeg dat elk een geziene-set nodig heeft.
3. Geef de blokindexformule en leg die uit met één voorbeeld.
4. Schrijf de enkele pass en de vroege return.
5. Noem de complexiteit en bied de bitmask-versie aan als erom gevraagd wordt.

Ik heb de bovenstaande code getest tegen een gewone rij-, kolom- en blokcontrole op 20.000 willekeurige borden, sommige geldig en sommige opzettelijk kapot, voordat ik publiceerde. Zo'n snelle willekeurige controle is een goede gewoonte tijdens het oefenen.

Gerelateerde oefening

Zie onze Big O cheat sheet voor de complexiteitstermen, de LeetCode Blind 75 list voor wat je hierna moet oefenen, en de coding interview assistant guide voor hoe je oefent.

Praat je aanpak hardop door terwijl je codeert. Een transcript laat zien of je de belangrijkste observatie noemde voordat je begon te schrijven. Volg de regels van de werkgever over AI-tools bij elke live assessment.