Sudoku Solver
Una griglia di sudoku è una griglia 9 × 9 divisa in nove riquadri 3 × 3. In una griglia risolta, ogni riga, ogni colonna e ogni riquadro contiene ciascuna cifra da 1 a 9 esattamente una volta.
Il puzzle è fornito come 9 stringhe, una per ogni riga dall’alto; un . indica una cella vuota. Riempi tutte le celle vuote e restituisci la griglia risolta nella stessa forma. La griglia ha esattamente una soluzione.
Funzione
- boardstring-array
- le 9 righe del puzzle, un punto in ogni cella vuota
- Restituiscestring-array
- le 9 righe della griglia risolta
Vincoli
boardcontiene 9 stringhe di lunghezza 9.- Ogni carattere è
.oppure una delle cifre da1a9. - Le cifre date non si ripetono mai all'interno di una riga, di una colonna o di un riquadro.
- La scacchiera ha esattamente una soluzione.
Esempi
- Input
- board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
- Output
- ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
- Spiegazione
- La riga superiore
9.7.....6contiene già 9, 7 e 6, quindi le sue sei celle vuote prendono 1, 2, 3, 4, 5 e 8. Le colonne e i riquadri determinano dove va ciascuno, e la riga diventa957214386.
Per approfondire
In un killer sudoku, anche le gabbie di celle devono dare come somma i valori indicati. Come aggiungeresti questa regola alla ricerca e la useresti per potare i rami in anticipo?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Tieni traccia delle cifre già presenti in ogni riga, in ogni colonna e in ogni riquadro 3 × 3. Così potrai determinare in O(1) se una cifra può essere inserita in una cella vuota.
Riempi le celle vuote una alla volta. Prova tutte le cifre che possono andare nella cella, passa alla cella successiva e annulla la cifra se con essa non è possibile completare il resto della griglia.
L’ordine delle celle è importante. Riempi per prima la cella vuota con il minor numero di cifre rimaste: una cella con una sola opzione non richiede diramazioni, mentre una cella senza opzioni ti dice subito di tornare indietro.
Soluzione
Risolvi con il backtracking: inserisci una cifra adatta, continua e annullala quando non è possibile completare la griglia. L’ordine delle celle determina la velocità. Su una griglia difficile, l’ordine di lettura può portare a visitare centinaia di milioni di griglie parziali; riempire per prima la cella con il minor numero di opzioni ne richiede circa un centinaio.
Backtracking nell'ordine di lettura
Corretto, ma non termina sui test più grandi
Intuizione
Riempi le celle vuote in ordine di lettura, ciascuna con la cifra più piccola che ci sta. Quando non rimangono cifre per una cella, torna alla cella precedente e prova la successiva. Ogni combinazione che rispetta le regole viene provata a turno, così la ricerca trova la soluzione.
Tre tabelle rendono O(1) ogni verifica di compatibilità: rowUsed[r][d], colUsed[c][d] e boxUsed[b][d], con box b = (r / 3) * 3 + c / 3. Inserire una cifra imposta tre valori e rimuoverla li azzera.
L’ordine fisso è il punto debole: la ricerca può riempire un’intera riga con cifre che ci stanno localmente e scoprire solo in seguito che lasciano molte celle senza possibilità. Una griglia le cui righe in alto hanno quasi nessun indizio, con cifre alte come soluzioni, la porta a esaminare oltre 300 milioni di griglie parziali.
Algoritmo
- Leggi la griglia in una matrice con 0 per una cella vuota, riempi
rowUsed,colUsedeboxUseded elenca le celle vuote in ordine di lettura. backtrack(k): sekè uguale al numero di celle vuote, restituisci true.- Per ogni cifra
dda 1 a 9 non utilizzata nella riga, nella colonna e nel riquadro della cellak, inseriscila, contrassegnala e restituisci true se lo fabacktrack(k+1); altrimenti rimuovi il contrassegno. - Se nessuna cifra funziona, svuota la cella e restituisci false. Chiama
backtrack(0)e riconverti la griglia in stringhe.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# row_used[r][d] is True when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
row_used = [[False] * 10 for _ in range(9)]
col_used = [[False] * 10 for _ in range(9)]
box_used = [[False] * 10 for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
else:
empties.append((r, c))
def backtrack(k):
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
grid[r][c] = d
row_used[r][d] = col_used[c][d] = box_used[b][d] = True
if backtrack(k + 1):
return True
row_used[r][d] = col_used[c][d] = box_used[b][d] = False
grid[r][c] = 0
return False
backtrack(0)
return ["".join(str(d) for d in row) for row in grid]Riempi prima la cella più vuota
Intuizione
La soluzione non dipende dall’ordine di riempimento, quindi scegli l’ordine che mantiene ridotta la ricerca: a ogni passaggio, riempi la cella vuota che consente il minor numero di cifre. Una cella con una sola cifra consentita è obbligata e non aggiunge rami. Una cella senza cifre consentite viene scelta subito, così una griglia errata viene individuata immediatamente.
Per contare rapidamente le cifre consentite per 81 celle a ogni passaggio, memorizza ogni riga, colonna e riquadro come maschera di bit: il bit d di rows[r] è impostato quando la cifra d si trova nella riga r. Una cella consente ~(rows[r] | cols[c] | boxes[b]) & 0x3FE, dove 0x3FE mantiene i bit da 1 a 9, e il conteggio è il numero di bit impostati. Inserendo d, imposta il bit d in tre maschere; un OR esclusivo lo rimuove.
Algoritmo
- Costruisci la griglia e le maschere
rows,colseboxesa partire dalle cifre date. backtrack(): esegui la scansione di tutte le celle, calcola le cifre consentite per ciascuna cella vuota e mantieni la prima cella con il numero minore. Se non ci sono celle vuote, restituisci true.- Per ogni cifra consentita di quella cella, inseriscila, imposta il relativo bit nelle tre maschere e restituisci true se
backtrack()lo fa; altrimenti cancella i bit. - Se nessuna cifra funziona, svuota la cella e restituisci false. Chiama
backtrack()e riconverti la griglia in stringhe.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# Bit d of rows[r] is set when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
rows[r] |= 1 << d
cols[c] |= 1 << d
boxes[(r // 3) * 3 + c // 3] |= 1 << d
def backtrack():
# Pick the empty cell with the fewest digits left (the first one on a tie).
best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
# Bits 1 to 9 of 0x3FE are the nine digits.
allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
count = bin(allowed).count("1")
if count < best_count:
best_r, best_c, best_allowed, best_count = r, c, allowed, count
if best_r == -1:
return True # no empty cell is left: the board is solved
r, c = best_r, best_c
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
bit = 1 << d
if best_allowed & bit:
grid[r][c] = d
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
if backtrack():
return True
rows[r] ^= bit
cols[c] ^= bit
boxes[b] ^= bit
grid[r][c] = 0
return False
backtrack()
return ["".join(str(d) for d in row) for row in grid]
Trappole e casi limite
- Dimenticare di cancellare una cifra dai registri di riga, colonna e riquadro quando la annulli. Le celle successive considerano quindi la cifra già usata e la ricerca non trova la soluzione.
- Usare
r / 3 + c / 3per il riquadro. Le celle(0, 4)e(4, 0)ottengono entrambe 1, quindi due riquadri condividono lo stesso registro e la griglia non può mai essere completata. Usa(r / 3) * 3 + c / 3con la divisione intera. - Non fermarsi alla prima soluzione. I passaggi di annullamento svuotano quindi di nuovo la griglia prima che tu la legga.
Domande frequenti3
Qual è la complessità temporale di un risolutore di sudoku con backtracking?
Esponenziale nel caso peggiore, O(9^m) per m celle vuote, perché ogni cella può diramarsi in un massimo di 9 cifre. Nei puzzle reali, le regole di riga, colonna e riquadro eliminano la maggior parte dei rami, e riempire per prima la cella più vuota elimina gran parte dei rimanenti.
Come si verifica che un sudoku abbia esattamente una soluzione?
Esegui la stessa ricerca con backtracking, ma conta le soluzioni e fermati quando il conteggio raggiunge 2. Un conteggio di 1 significa che il puzzle ha una soluzione unica, 0 significa che non ha soluzioni. I generatori di puzzle eseguono questo controllo dopo aver rimosso ogni indizio.
C'è un modo più veloce del backtracking per risolvere il sudoku?
La maggior parte di chi risolve velocemente ricorre comunque al backtracking, ma deduce di più prima di ogni tentativo. La propagazione dei vincoli riempie ogni cella con una sola opzione e inserisce ogni cifra che può stare in una sola cella della riga, della colonna o del riquadro, poi ripete il processo. Il Sudoku può anche essere formulato come un problema di copertura esatta e risolto con l'Algoritmo X di Knuth.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def solveSudoku(board):
# Scrivi il codice quiTest #1
Argomento
board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
Output atteso
["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]