Studia attentamente questo codice e scopri un modo intelligente per usare la ricorsione per risolvere quei complicati sudoku.
Il Sudoku è un popolare rompicapo numerico che consiste in una griglia 9x9 con cifre da 1 a 9. Il puzzle include una combinazione di numeri e alcuni spazi vuoti, che devi riempire.
Quando si riempiono gli spazi vuoti, ogni riga, colonna e griglia secondaria 3x3 deve contenere tutte le cifre da 1 a 9.
Un semplice script Python può aiutarti a risolvere un puzzle di Sudoku per te. Può analizzare tutti gli spazi vuoti sulla scheda Sudoku e trovare un possibile numero da riempire in ogni spazio vuoto.
Come creare e visualizzare la scheda Sudoku
All'interno di uno script Python, dovrai utilizzare un elenco di array per memorizzare i valori del puzzle Sudoku irrisolto.
Il codice utilizzato in questo progetto è disponibile in this Repository GitHub con licenza MIT.
- All'interno di un nuovo script Python chiamato sudoku.py, memorizza tutti i valori per la griglia 9x9. Ogni riga e colonna rappresenta i nove numeri attraverso e lungo il puzzle Sudoku. Aggiungi 0 per rappresentare gli spazi che devono essere risolti:
tavola = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
] - All'interno di una nuova funzione chiamata print_board, usa un ciclo for per elaborare ogni riga nella griglia:
defprint_board(asse):
per riga In allineare(9): - Per separare ogni riga in terzi, controlla se la riga è divisibile per tre e aggiungi una riga:
Se riga % 3 == 0E fila != 0:
stampa("- - - - - - - - - - - - - - ") - All'interno di ogni riga, scorrere ogni colonna. Puoi anche dividere le colonne in terzi controllando se la colonna è divisibile per tre:
per col In allineare(9):
Se colonna % 3 == 0E col != 0:
stampa(" | ", fine="") - Stampa il valore numerico memorizzato nella griglia. Se la colonna è l'ultima colonna per quella particolare riga, aggiungi una linea di interruzione, in modo che la seguente riga appaia su una nuova riga:
Se colonna == 8:
stampa (scheda[riga][col])
altro:
print (str (scheda[riga][col]) + " ", fine="") - Chiama la funzione per stampare la scheda:
print_board (scheda) - In una riga di comando, vai alla cartella in cui hai memorizzato il tuo script python, ad esempio:
CD Desktop - Usa il comando python per eseguire il tuo script Sudoku. Guarda il puzzle stampato sullo schermo:
python sudoku.py
Come identificare gli spazi vuoti da risolvere
Puoi scorrere gli elenchi per trovare gli spazi composti da 0. Questi determinano quali spazi dovevano essere risolti.
- In una nuova funzione chiamata find_empty(), scorre ogni riga e colonna sulla lavagna:
deftrova_vuoto(asse):
per riga In allineare(9):
per col In allineare(9): - Se il valore della cella corrente è 0, restituisce la posizione corrente della cella vuota:
Se scheda[riga][col] == 0:
ritorno (riga, colonna) - Se lo script raggiunge la fine della funzione, significa che lo script non è riuscito a trovare alcuna cella con il valore 0. In questo caso, non restituire nulla:
ritornoNessuno - In una nuova funzione chiamata solve(), usa la funzione find per trovare il primo spazio vuoto sulla lavagna:
defrisolvere(asse):
trova = trova_vuoto (scheda) - La funzione find_empty() restituisce la posizione della cella in formato tupla, ad esempio (0, 2). Salva questi valori separatamente nel file riga E col variabili. Altrimenti, restituisci true per indicare che non ci sono più spazi vuoti da risolvere:
Senon Trovare:
ritornoVERO
altro:
riga, col = trova
Come risolvere il puzzle per ogni riga, colonna e griglia 3x3
Ora che puoi identificare il primo spazio vuoto da risolvere, dovrai provare a trovare un numero appropriato per riempire quello spazio e risolvere il puzzle.
Usando la ricorsione, chiama la funzione solve() al suo interno per provare ogni possibile combinazione di valori anche per tutti gli altri spazi.
- All'interno della funzione solve(), dopo aver trovato il primo spazio vuoto, scorrere ogni numero da 1 a 9. Questi numeri rappresentano i possibili numeri che potrebbero riempire lo spazio irrisolto:
per num In allineare(1, 10): - Inserisci la scheda, il numero possibile e la posizione della cella vuota in una nuova funzione. La nuova funzione restituirà vero se quel numero è un numero valido che può risolvere quello spazio vuoto. Se è valido, assegna quel numero alla cella sulla lavagna:
Se is_valid (scheda, num, (riga, colonna)):
board[row][col] = num - Crea la funzione is_valid(), con i parametri corrispondenti:
defè valido(scheda, num, pos): - Usa la funzione per verificare se posizionare il numero in quella posizione viola le regole del gioco Sudoku. Innanzitutto, controlla se quel numero esiste già nella riga o nella colonna della cella:
per col In allineare(9):
Se scheda[pos[0]][col] == num E posizione[1] != colonna:
ritornoFalsoper riga In allineare(9):
Se bacheca[riga][pos[1]] == num E posizione[0] != riga:
ritornoFalso - Ottieni la griglia 3x3 a cui appartiene la cella. Puoi farlo dividendo la posizione della cella per tre:
box_row = pos[0] // 3
box_col = pos[1] // 3 - Per ogni riga e colonna in quella griglia 3x3, controlla se il numero esiste già. In caso affermativo, restituire false:
per riga In intervallo (box_row*3, casella_riga*3 + 3):
per col In intervallo (box_col*3, box_col*3 + 3):
Se board[row][col] == num E (riga, colonna) != pos:
ritornoFalso - Se lo script raggiunge la fine della funzione, significa che nessuna delle regole del Sudoku ha fallito. Restituisci vero:
ritornoVERO - La funzione is_valid() controlla solo se il posizionamento del numero è valido, ma ciò non significa che sia la risposta corretta alla soluzione complessiva. All'interno della funzione solve(), chiama nuovamente la funzione solve() con la scheda aggiornata. La funzione solve() può raggiungere uno stato in cui non può più utilizzare alcun numero per riempire gli spazi. In questo caso, l'intera funzione restituisce false, reimposta quella particolare cella su 0 e torna indietro. La funzione solve() restituisce true solo quando lo script può riempire tutti gli spazi:
per num In allineare(1, 10):
Se is_valid (scheda, num, (riga, colonna)):
board[row][col] = num
Se risolvere (tavola):
ritornoVERO
scheda[riga][col] = 0ritornoFalso - Per iniziare a risolvere il puzzle, chiama la funzione solve() con la scheda originale, in fondo allo script, dopo aver dichiarato la funzione solve():
risolvere (tavola) - Stampa il risultato finale:
stampa("Risolto:")
print_board (scheda) - Sulla riga di comando, utilizzare il comando python per eseguire nuovamente lo script. Visualizza il puzzle risolto stampato sullo schermo:
python sudoku.py
Creazione di giochi utilizzando Python
Sudoku è solo uno dei tanti giochi che puoi creare e risolvere usando Python. Puoi usare Python per creare vari altri giochi, come un guazzabuglio di parole, un gioco di avventura basato su testo o un gioco di colori, solo per citarne alcuni.