Valid Sudoku

Q: Come fai a trovare in quale riquadro 3 × 3 si trova una cella?

Con la divisione intera, r / 3 indica la fascia di righe (0, 1 o 2) e c / 3 indica la pila di colonne. (r / 3) * 3 + c / 3 numera i riquadri da 0 a 8, da sinistra a destra e dall'alto verso il basso. La cella (7, 1) si trova nel riquadro 2 * 3 + 0 = 6 , quello in basso a sinistra.

MedioHashing

+10

Ricevi una griglia di Sudoku 9 × 9 come board, un elenco di 9 stringhe di 9 caratteri ciascuna, una stringa per riga. Ogni carattere è una cifra da 1 a 9 oppure . per una cella vuota. Restituisci true se nessuna cifra compare due volte nella stessa riga, nella stessa colonna o nello stesso riquadro 3 × 3, e false altrimenti. Vengono controllate solo le celle riempite: la griglia non deve necessariamente essere risolvibile.

Funzione

isValidSudoku(board: string-array) → boolean

boardstring-array: 9 stringhe di 9 caratteri, una per riga, cifre da 1 a 9 e . per una cella vuota
Restituisceboolean: true se nessuna riga, colonna o riquadro 3 × 3 ripete una cifra, false altrimenti

Vincoli

board.length == 9 e board[i].length == 9
board[i][j] è una cifra da 1 a 9 oppure .
Potrebbe essere impossibile completare la tavola; contano solo le ripetizioni tra le celle riempite.

Esempi

Input: board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Output: true
Spiegazione: Ogni riga, colonna e riquadro contiene ogni cifra al massimo una volta. La riga 4 (contando da 0), .74..89.3, contiene una sola volta ciascuna delle cifre 7, 4, 8, 9 e 3, e lo stesso vale per gli altri 26 gruppi, quindi la risposta è true.

Input: board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
Output: false
Spiegazione: La riga 0 e la riga 7 iniziano entrambe con un 3, quindi la colonna 0 contiene due 3. Le due celle si trovano in righe diverse e in riquadri diversi; solo il controllo della colonna rileva questo caso.

Input: 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"]
Output: false
Spiegazione: Il 5 alla riga 0, colonna 8 e il 5 alla riga 2, colonna 7 si trovano in righe diverse e colonne diverse, ma entrambi sono nel riquadro in alto a destra, quindi la risposta è false.

+16 test nascosti all’invio

Per approfondire

Generalizza il controllo per una griglia 16 × 16 con riquadri 4 × 4 e i simboli da 1 a 9 e da A a G. Quali numeri nel tuo codice dipendono dalle dimensioni della griglia e come diventa la formula per il riquadro?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ogni cifra appartiene contemporaneamente a tre gruppi: la sua riga, la sua colonna e il suo riquadro 3 × 3. Le righe e le colonne si indicizzano direttamente; è nel riquadro che si annida la maggior parte dei bug. Numera i riquadri da 0 a 8 con (r / 3) * 3 + c / 3 e una sola passata sulle 81 celle può controllare insieme tutti e 27 i gruppi.

Controlla ogni riga, colonna e riquadro separatamente

Intuizione

Le regole definiscono 27 gruppi: 9 righe, 9 colonne e 9 riquadri. Raccogli le nove celle di ciascun gruppo e controlla se tra queste si ripete una cifra, ignorando i punti. Se nessun gruppo contiene ripetizioni, la griglia è valida.

La riga i è board[i][0..8] e la colonna i è board[0..8][i]. Il riquadro i inizia alla riga 3 * (i / 3) e alla colonna 3 * (i % 3), usando la divisione intera; quindi il riquadro 5 inizia alla riga 3, colonna 6. La sua cella k si trova k / 3 righe più in basso e k % 3 colonne più a destra rispetto a quell’angolo.

Per trovare una ripetizione tra nove celle, mantieni un flag per ogni cifra che indica se è già stata vista e fermati alla prima cifra il cui flag è già impostato. Ognuna delle 81 celle viene letta tre volte, una per ciascun gruppo a cui appartiene: 243 letture, una quantità di lavoro fissa. Su una griglia n × n, lo stesso metodo richiede O(n²).

Algoritmo

Per i da 0 a 8, raccogli la riga i, la colonna i e il riquadro i, nove celle ciascuno.
Il riquadro i inizia da top = 3 * (i / 3) e left = 3 * (i % 3); la sua cella k si trova alla riga top + k / 3, colonna left + k % 3.
Per ogni gruppo, percorri le sue celle con indicatori «visto» nuovi, saltando i punti.
Se una cifra è già contrassegnata, restituisci false.
Dopo tutti i 27 gruppi, restituisci 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

Un passaggio con una tabella degli elementi visti per ogni riga, colonna e riquadro

Intuizione

Invece di raccogliere i gruppi, visita ogni cella una volta e poni tutte e tre le domande contemporaneamente. Tieni tre tabelle di flag 9 × 9: seenRow[r][d] indica che la cifra d+1 è già presente nella riga r, mentre seenCol e seenBox funzionano allo stesso modo per colonne e riquadri.

La cella (r, c) appartiene al riquadro (r / 3) * 3 + c / 3. La prima parte individua la fascia di tre riquadri (le righe da 0 a 2 danno la fascia 0, le righe da 3 a 5 la fascia 1, le righe da 6 a 8 la fascia 2), mentre c / 3 individua il riquadro all'interno della fascia. La cella (4, 7) finisce nel riquadro 1 * 3 + 2 = 5, quello centrale a destra.

Per ogni cella riempita, se uno dei suoi tre flag è già impostato, la cifra si ripete in quel gruppo e restituisci subito false. Altrimenti, imposta tutti e tre i flag. Ogni cella viene letta una volta e le tabelle contengono 243 flag, quindi il tempo e la memoria sono costanti per una griglia 9 × 9 e O(n²) per una griglia n × n.

Algoritmo

Crea seenRow, seenCol e seenBox, ciascuno di 9 × 9 e tutti impostati su false.
Visita ogni cella (r, c); saltala se contiene un punto.
Sia d la cifra meno 1 e b = (r / 3) * 3 + c / 3.
Se seenRow[r][d], seenCol[c][d] o seenBox[b][d] è true, restituisci false.
Altrimenti imposta tutti e tre su true. Dopo l'ultima cella, restituisci 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

Trappole e casi limite

I controlli di righe e colonne raramente vanno storti. Gli errori riguardano l'indice del riquadro e cosa viene considerato una ripetizione.

Calcolare il riquadro come r / 3 + c / 3. Si ottengono solo valori da 0 a 4, quindi le celle (0, 3) e (3, 0) condividono un numero pur trovandosi in riquadri diversi, e due 7 in quelle celle vengono segnalati come una ripetizione. Usa (r / 3) * 3 + c / 3.
Dividere con / in JavaScript, Python 3 o Lua, dove 4 / 3 è 1.33, non un numero di riquadro. Usa Math.floor, // o math.floor.
Considerare . un valore. Una griglia vuota ha nove punti in ogni riga ed è valida.
Cercare di risolvere il rompicapo. Con 12345678. come riga 0 e un 9 più in basso nella colonna 8, l'ultima cella della riga 0 non potrà mai essere riempita, eppure nessun gruppo ripete una cifra, quindi la risposta è true.
Controllare righe e colonne ma non i riquadri. Una griglia completa in cui ogni riga è la precedente spostata di una posizione verso sinistra non presenta ripetizioni in alcuna riga o colonna, mentre ogni riquadro contiene ripetizioni.

Domande frequenti4

Qual è la complessità temporale di Valid Sudoku?

La griglia ha sempre 81 celle, quindi entrambi gli approcci richiedono un tempo O(1) e usano una memoria O(1). Per un Sudoku generale n × n, il controllo in un solo passaggio legge ciascuna delle n² celle una volta e mantiene 3n² flag, quindi richiede O(n²) sia in termini di tempo sia di memoria.

Una griglia di Sudoku valida deve essere risolvibile?

No. Valido qui significa solo che nessuna cifra si ripete in una riga, una colonna o un riquadro 3 × 3 tra le celle già riempite. Una griglia può superare questo controllo e comunque non avere soluzioni. Per determinare se è risolvibile serve una ricerca, ad esempio il backtracking, che è un problema diverso.

Come fai a trovare in quale riquadro 3 × 3 si trova una cella?

Con la divisione intera, r / 3 indica la fascia di righe (0, 1 o 2) e c / 3 indica la pila di colonne. (r / 3) * 3 + c / 3 numera i riquadri da 0 a 8, da sinistra a destra e dall'alto verso il basso. La cella (7, 1) si trova nel riquadro 2 * 3 + 0 = 6, quello in basso a sinistra.

Si può risolvere il Sudoku valido con le maschere di bit?

Sì. Assegna a ogni riga, colonna e riquadro un intero e fai in modo che il bit d indichi che la cifra d+1 è stata vista. Per una cella riempita, calcola 1 << d; se il risultato dell’AND con una qualsiasi delle tre maschere è diverso da zero, la cifra si ripete, altrimenti esegui l’OR nelle tre maschere. Sono 27 interi invece di 243 flag, con la stessa logica a un solo passaggio.

Python

def isValidSudoku(board):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

true