Risolutore di Sudoku ricorsivo utilizzando Python
Un risolutore di Sudoku che funziona in modo ricorsivo. Apprezzerei i tuoi commenti sullo stile di codifica, sulla struttura e su come migliorarlo. La ringrazio molto per il vostro tempo.
Struttura del codice
Il Risolutore funziona accettando una stringa di 81 cifre per l'input del puzzle Sudoku. Gli zeri vengono considerati come celle vuote. Lo analizza in un array Numpy 9x9.
La get_candidatesfunzione crea elenchi di possibili cifre per riempire ogni cella seguendo le regole del Sudoku (non si ripetono 1-9 cifre lungo righe, colonne e sottogriglie 3x3).
La funzione principale del risolutore è solve. Primo, scarta i candidati sbagliati con la filter-candidatesfunzione. I "candidati sbagliati" sono quelli che, quando riempiti in una cella vuota, hanno portato a un'altra cella che non ha più candidati altrove sulla griglia del Sudoku.
Dopo aver filtrato i candidati, fill_singlesviene chiamato a riempire le celle vuote che hanno un solo candidato rimanente. Se questo processo porta a una griglia Sudoku completamente riempita, viene restituita come soluzione. C'è una clausola per restituire Noneche viene utilizzata per eseguire il backtrack delle modifiche dalla make_guessfunzione. Questa funzione riempirà la successiva cella vuota con il minor numero di candidati con uno dei suoi candidati, un valore "ipotetico". Quindi chiama solvein modo ricorsivo per trovare una soluzione o raggiungere una griglia senza soluzione (nel qual caso solveritorna Nonee le modifiche dell'ultima ipotesi vengono annullate).
from copy import deepcopy
import numpy as np
def create_grid(puzzle_str: str) -> np.ndarray:
"""Create a 9x9 Sudoku grid from a string of digits"""
# Deleting whitespaces and newlines (\n)
lines = puzzle_str.replace(' ','').replace('\n','')
digits = list(map(int, lines))
# Turning it to a 9x9 numpy array
grid = np.array(digits).reshape(9,9)
return grid
def get_subgrids(grid: np.ndarray) -> np.ndarray:
"""Divide the input grid into 9 3x3 sub-grids"""
subgrids = []
for box_i in range(3):
for box_j in range(3):
subgrid = []
for i in range(3):
for j in range(3):
subgrid.append(grid[3*box_i + i][3*box_j + j])
subgrids.append(subgrid)
return np.array(subgrids)
def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""
def subgrid_index(i, j):
return (i//3) * 3 + j // 3
subgrids = get_subgrids(grid)
grid_candidates = []
for i in range(9):
row_candidates = []
for j in range(9):
# Row, column and subgrid digits
row = set(grid[i])
col = set(grid[:, j])
sub = set(subgrids[subgrid_index(i, j)])
common = row | col | sub
candidates = set(range(10)) - common
# If the case is filled take its value as the only candidate
if not grid[i][j]:
row_candidates.append(list(candidates))
else:
row_candidates.append([grid[i][j]])
grid_candidates.append(row_candidates)
return grid_candidates
def is_valid_grid(grid : np.ndarray) -> bool:
"""Verify the input grid has a possible solution"""
candidates = get_candidates(grid)
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 0:
return False
return True
def is_solution(grid : np.ndarray) -> bool:
"""Verify if the input grid is a solution"""
if np.all(np.sum(grid, axis=1) == 45) and \
np.all(np.sum(grid, axis=0) == 45) and \
np.all(np.sum(get_subgrids(grid), axis=1) == 45):
return True
return False
def filter_candidates(grid : np.ndarray) -> list:
"""Filter input grid's list of candidates"""
test_grid = grid.copy()
candidates = get_candidates(grid)
filtered_candidates = deepcopy(candidates)
for i in range(9):
for j in range(9):
# Check for empty cells
if grid[i][j] == 0:
for candidate in candidates[i][j]:
# Use test candidate
test_grid[i][j] = candidate
# Remove candidate if it produces an invalid grid
if not is_valid_grid(fill_singles(test_grid)):
filtered_candidates[i][j].remove(candidate)
# Revert changes
test_grid[i][j] = 0
return filtered_candidates
def merge(candidates_1 : list, candidates_2 : list) -> list:
"""Take shortest candidate list from inputs for each cell"""
candidates_min = []
for i in range(9):
row = []
for j in range(9):
if len(candidates_1[i][j]) < len(candidates_2[i][j]):
row.append(candidates_1[i][j][:])
else:
row.append(candidates_2[i][j][:])
candidates_min.append(row)
return candidates_min
def fill_singles(grid : np.ndarray, candidates=None) -> np.ndarray:
"""Fill input grid's cells with single candidates"""
grid = grid.copy()
if not candidates:
candidates = get_candidates(grid)
any_fill = True
while any_fill:
any_fill = False
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 1 and grid[i][j] == 0:
grid[i][j] = candidates[i][j][0]
candidates = merge(get_candidates(grid), candidates)
any_fill = True
return grid
def make_guess(grid : np.ndarray, candidates=None) -> np.ndarray:
"""Fill next empty cell with least candidates with first candidate"""
grid = grid.copy()
if not candidates:
candidates = get_candidates(grid)
# Getting the shortest number of candidates > 1:
min_len = sorted(list(set(map(
len, np.array(candidates).reshape(1,81)[0]))))[1]
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == min_len:
for guess in candidates[i][j]:
grid[i][j] = guess
solution = solve(grid)
if solution is not None:
return solution
# Discarding a wrong guess
grid[i][j] = 0
def solve(grid : np.ndarray) -> np.ndarray:
"""Recursively find a solution filtering candidates and guessing values"""
candidates = filter_candidates(grid)
grid = fill_singles(grid, candidates)
if is_solution(grid):
return grid
if not is_valid_grid(grid):
return None
return make_guess(grid, candidates)
# # Example usage
# puzzle = """100920000
# 524010000
# 000000070
# 050008102
# 000000000
# 402700090
# 060000000
# 000030945
# 000071006"""
# grid = create_grid(puzzle)
# solve(grid)
```
Risposte
Sono riuscito a migliorare le prestazioni del programma di circa il 900% senza capire o modificare gran parte dell'algoritmo in circa un'ora. Ecco cosa ho fatto:
Prima di tutto, hai bisogno di un benchmark. È molto semplice, basta programmare il tempo
start = time.time()
solve(grid)
print(time.time()-start)
Sul mio computer ci sono voluti circa 4,5 secondi. Questa è la nostra linea di base.
La prossima cosa è fare il profilo. Lo strumento che ho scelto è VizTracer, sviluppato da me :)https://github.com/gaogaotiantian/viztracer
VizTracer genererà un report HTML (o json che potrebbe essere caricato da chrome :: // tracing) della sequenza temporale dell'esecuzione del codice. Sembra questo nella tua versione originale:
Come puoi vedere, ci sono molte chiamate lì. La cosa che dobbiamo fare è capire qual è il collo di bottiglia qui. La struttura non è complicata, molti fill_singlesvengono chiamati e dobbiamo ingrandire per verificare cosa c'è dentro.
È molto chiaro che get_candidatesè la funzione che ha causato la maggior parte del tempo fill_singles, che occupa la maggior parte della sequenza temporale. Quindi questa è la funzione che vogliamo prima dare un'occhiata.
def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""
def subgrid_index(i, j):
return (i//3) * 3 + j // 3
subgrids = get_subgrids(grid)
grid_candidates = []
for i in range(9):
row_candidates = []
for j in range(9):
# Row, column and subgrid digits
row = set(grid[i])
col = set(grid[:, j])
sub = set(subgrids[subgrid_index(i, j)])
common = row | col | sub
candidates = set(range(10)) - common
# If the case is filled take its value as the only candidate
if not grid[i][j]:
row_candidates.append(list(candidates))
else:
row_candidates.append([grid[i][j]])
grid_candidates.append(row_candidates)
return grid_candidates
La cosa che ha attirato la mia prima attenzione è stata la fine del tuo ciclo for nidificato. Hai controllato se grid[i][j]è pieno. Se lo è, allora è l'unico candidato. Tuttavia, se è pieno, non ha nulla a che fare con ciò candidatesche hai calcolato molto duramente nel tuo ciclo for annidato.
Quindi la prima cosa che ho fatto è stata spostare il segno di spunta all'inizio del ciclo for.
for i in range(9):
row_candidates = []
for j in range(9):
if grid[i][j]:
row_candidates.append([grid[i][j]])
continue
# Row, column and subgrid digits
row = set(grid[i])
col = set(grid[:, j])
sub = set(subgrids[subgrid_index(i, j)])
common = row | col | sub
candidates = set(range(10)) - common
row_candidates.append(list(candidates))
Questa ottimizzazione da sola ha dimezzato il tempo di esecuzione, ora siamo a circa 2,3 secondi.
Poi ho notato che nel tuo ciclo for annidato stai facendo molte operazioni ridondanti sugli insiemi. Anche row / col / sub deve essere calcolato solo 9 volte, lo stai calcolando 81 volte, il che è piuttosto negativo. Quindi ho spostato il calcolo fuori dal ciclo for.
def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""
def subgrid_index(i, j):
return (i//3) * 3 + j // 3
subgrids = get_subgrids(grid)
grid_candidates = []
row_sets = [set(grid[i]) for i in range(9)]
col_sets = [set(grid[:, j]) for j in range(9)]
subgrid_sets = [set(subgrids[i]) for i in range(9)]
total_sets = set(range(10))
for i in range(9):
row_candidates = []
for j in range(9):
if grid[i][j]:
row_candidates.append([grid[i][j]])
continue
# Row, column and subgrid digits
row = row_sets[i]
col = col_sets[j]
sub = subgrid_sets[subgrid_index(i, j)]
common = row | col | sub
candidates = total_sets - common
# If the case is filled take its value as the only candidate
row_candidates.append(list(candidates))
grid_candidates.append(row_candidates)
return grid_candidates
Questo ha ridotto il tempo di esecuzione a circa 1,5 secondi. Nota che non ho ancora provato a capire il tuo algoritmo. L'unica cosa che ho fatto è stato usare VizTracer per trovare la funzione che deve essere ottimizzata e fare la trasformazione della stessa logica. Ho migliorato le prestazioni di circa il 300% in circa 15 minuti.
A questo punto, l'overhead di VizTracer su WSL è significativo, quindi ho disattivato la traccia della funzione C. Sono rimaste solo le funzioni Python e il sovraccarico è stato di circa il 10%.
Ora che è get_candidatesstato migliorato (anche se può essere fatto meglio), dobbiamo fare un quadro più ampio di questo. Quello che posso osservare dal risultato di VizTracer è stato che ha fill_singleschiamato get_candidatesmolto frequentemente, troppe chiamate. (Questo è qualcosa che è difficile da notare su cProfiler)
Quindi il passo successivo è stato capire se possiamo effettuare fill_singleschiamate get_candidatesmeno spesso. Qui richiede un certo livello di comprensione dell'algoritmo.
while any_fill:
any_fill = False
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 1 and grid[i][j] == 0:
grid[i][j] = candidates[i][j][0]
candidates = merge(get_candidates(grid), candidates)
any_fill = True
Sembra che qui tu abbia tentato di riempire uno spazio vuoto con un solo candidato e ricalcolare i candidati dell'intera griglia, quindi trovare lo spazio vuoto successivo con un candidato. Questo è un metodo valido, ma ha causato troppe chiamate a get_candidates. Se ci pensi, quando riempiamo uno spazio vuoto con un numero n, tutti gli altri spazi con un solo candidato che non è nnon saranno interessati. Quindi durante un passaggio della griglia, potremmo effettivamente provare a riempire più spazi vuoti, a patto di non riempire lo stesso numero due volte. In questo modo, possiamo chiamare get_candidatesmeno spesso, il che è un enorme consumatore di tempo. Ho usato un set per farlo.
filled_number = set()
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 1 and grid[i][j] == 0 and candidates[i][j][0] not in filled_number:
grid[i][j] = candidates[i][j][0]
filled_number.add(candidates[i][j][0])
any_fill = True
candidates = merge(get_candidates(grid), candidates)
Ciò ha portato il tempo di esecuzione a 0,9 secondi.
Poi ho guardato il rapporto VizTracer, mi sono reso conto che fill_singlesè quasi sempre chiamato da filter_candidatese l'unica cosa che filter_candidatesinteressa, è se fill_singlesrestituisce una griglia valida. Questa è un'informazione che potremmo conoscere in anticipo, purché fill_singlestrovi una posizione senza candidati. Se torniamo presto, non è necessario calcolarlo get_candidatesmolte volte.
Quindi ho cambiato un po 'la struttura del codice, ho fatto fill_singlesritorno Nonese non riesce a trovare una griglia valida.
Finalmente sono riuscito a portare il tempo di esecuzione a 0,5 secondi, che è il 900% più veloce rispetto alla versione originale.
In realtà è stata un'avventura divertente perché stavo testando il mio progetto VizTracer e ho cercato di capire se fosse utile individuare la parte che richiedeva tempo. Ha funzionato bene :)
Numpyification
get_subgridsessenzialmente riorganizza un array numpy con un minimo di numpy. Potrebbe essere fatto con numpy stesso, ad esempio:
def get_subgrids(grid: np.ndarray) -> np.ndarray:
"""Divide the input grid into 9 3x3 sub-grids"""
swapped = np.swapaxes(np.reshape(grid, (3, 3, 3, 3)), 1, 2)
return np.reshape(swapped, (9, 9))
Il rovescio della medaglia, suppongo, è che scambiare i due assi centrali di un array 4D è un po 'complicato.
Prestazione
Quasi tutto il tempo viene speso get_candidates. Penso che le ragioni siano principalmente:
- Viene chiamato troppo spesso. Ad esempio, dopo aver compilato una cella (come in
fill_singles), invece di ricalcolare i candidati da zero, sarebbe più veloce rimuovere semplicemente il nuovo valore dai candidati nella stessa riga / colonna / casa. - Se una cella è piena, l'elenco dei candidati è solo il valore compilato, ma il costoso calcolo dell'insieme viene eseguito comunque. È facile da evitare spostando queste affermazioni all'interno del file
if.
Prestazioni algoritmiche
Questo risolutore utilizza solo Naked Singles come "tecnica di propagazione", l'aggiunta di Hidden Singles è nella mia esperienza un passo molto grande verso un risolutore efficiente.