Valid Sudoku
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 casella vuota. Restituisci true se nessuna cifra compare due volte in una riga, una colonna o un riquadro 3 × 3, e false altrimenti. Vengono controllate solo le caselle compilate: non è necessario che la griglia sia risolvibile.
Funzione
- 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 casella 3 × 3 ripete una cifra, false altrimenti
Vincoli
board.length == 9eboard[i].length == 9board[i][j]è una cifra da1a9oppure.- La scacchiera potrebbe essere impossibile da completare; 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
- La riga 4, contando da 0,
.74..89.3, contiene una volta ciascuno i numeri 7, 4, 8, 9 e 3, e nessuno degli altri 26 gruppi ripete una cifra.
- 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
- Sia la riga 0 sia la riga 7 iniziano con un
3, quindi la colonna 0 contiene due 3. Non condividono né una riga né un riquadro, quindi solo il controllo della colonna rileva il problema.
- 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
5alla riga 0, colonna 8 e il5alla riga 2, colonna 7 non condividono né la stessa riga né la stessa colonna, ma si trovano entrambi nel riquadro in alto a destra, quindi la risposta èfalse.
Per approfondire
Come controlleresti una griglia 16 × 16 con riquadri 4 × 4 e i simboli da 1 a 9 e da A a G? Come diventa la formula dei riquadri?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Elenca i gruppi di cui parlano le regole. Quanti sono e quale tipo è il più difficile da indicizzare?
La cella alla riga
re alla colonnacsi trova in una sola casella. Con la divisione intera,r / 3indica in quale fascia di tre righe si trova ec / 3in quale blocco di tre colonne. Combina i due valori in un unico numero da 0 a 8.Visita ogni cella una volta. Mantieni un indicatore di visita per ogni coppia (riga, cifra), (colonna, cifra) e (riquadro, cifra). Una cella riempita il cui indicatore è già impostato in uno dei suoi tre gruppi è una ripetizione.
Soluzione
Ogni cifra appartiene a tre gruppi: la sua riga, la sua colonna e il suo riquadro 3 × 3. Righe e colonne sono facili da indicizzare; è nel riquadro che si nascondono gli errori. Numera i riquadri da 0 a 8 con (r / 3) * 3 + c / 3 e un'unica scansione delle 81 celle controlla tutti i 27 gruppi.
Controlla separatamente ogni riga, colonna e riquadro
Intuizione
La regola nomina 27 gruppi: 9 righe, 9 colonne e 9 riquadri. Raccogli le nove celle di ciascun gruppo e cerca una cifra ripetuta, ignorando i punti. La griglia è valida esattamente quando nessun gruppo ne contiene una.
Un flag «visto» per ogni cifra individua una ripetizione tra le nove celle. Ognuna delle 81 celle viene letta una volta per ciascuno dei suoi tre gruppi: 243 letture, una quantità di lavoro fissa. Su una griglia n × n, lo stesso metodo ha un costo di O(n²).
Algoritmo
- Per
ida 0 a 8, raccogli la rigai, la colonnaie il riquadroi. - Il riquadro
iha l’angolo alla riga3 * (i / 3), colonna3 * (i % 3); la sua cellaksi trovak / 3righe più in basso ek % 3colonne più a destra. - Esamina ogni gruppo con indicatori di valori già visti appena inizializzati, ignorando i punti. Se una cifra è già segnata, 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 TrueUn passaggio con una tabella degli elementi già visti per ogni riga, colonna e riquadro
Intuizione
Visita ogni cella una volta e poni tutte e tre le domande insieme. 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.
La cella (r, c) appartiene al riquadro (r / 3) * 3 + c / 3. La prima parte individua la fascia di tre riquadri e c / 3 individua il riquadro all'interno della fascia. La cella (4, 7) si trova nel riquadro 1 * 3 + 2 = 5, quello centrale a destra.
Un flag già impostato significa che la cifra si ripete in quel gruppo. Ogni cella viene letta una volta e le tabelle contengono 243 flag: tempo e memoria costanti in questo caso, O(n²) su una griglia n × n.
Algoritmo
- Crea
seenRow,seenColeseenBox, ciascuno di dimensioni 9 × 9 e tutti impostati su false. - Per ogni cella compilata
(r, c), poniduguale alla sua cifra meno 1 eb = (r / 3) * 3 + c / 3. - Se
seenRow[r][d],seenCol[c][d]oseenBox[b][d]è impostato, restituiscifalse; altrimenti, imposta tutti e tre. - 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
- Calcolare il riquadro come
r / 3 + c / 3. Restituisce solo valori da 0 a 4, quindi(0, 3)e(3, 0)condividono un numero anche se appartengono a riquadri diversi, e due 7 lì vengono segnalati come una ripetizione. - Dividere con
/in JavaScript, Python 3 o Lua, dove4 / 3è1.33. Arrotonda per difetto. - Considerare
.un valore. Una griglia vuota, con nove punti per riga, è valida. - Cercare di risolvere il puzzle. Una riga 0 con
12345678.e un 9 più in basso nella colonna 8 non può mai essere completata, eppure non c'è alcuna ripetizione:true. - Ignorare i riquadri. Una griglia completa in cui ogni riga è quella sopra spostata a sinistra di una posizione non presenta ripetizioni nelle righe o nelle colonne, mentre ogni riquadro contiene ripetizioni.
Domande frequenti3
Qual è la complessità temporale di Valid Sudoku?
La griglia ha sempre 81 celle, quindi entrambi gli approcci richiedono tempo O(1) e 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: tempo e memoria O(n²).
Una griglia di Sudoku valida deve necessariamente 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 compilate. Una griglia può superare questo controllo e comunque non avere soluzione. Determinare se è risolvibile richiede una ricerca come il backtracking, che è un problema diverso.
Il Sudoku valido può essere risolto con le maschere di bit?
Sì. Assegna a ogni riga, colonna e riquadro un intero, in cui il bit d indica che la cifra d+1 è stata vista. Per una cella compilata, se 1 << d AND produce un valore diverso da zero con una qualsiasi delle sue tre maschere, la cifra si ripete; altrimenti applicalo con OR a tutte e tre. Sono 27 interi invece di 243 flag.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def isValidSudoku(board):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Output atteso
true