Pozorno preučite to kodo in odkrijte pameten način za uporabo rekurzije za reševanje teh zapletenih sudokujev.
Sudoku je priljubljena številska uganka, ki je sestavljena iz mreže 9x9 s števkami od 1 do 9. Uganka vključuje kombinacijo številk in nekaj praznih mest, ki jih morate zapolniti.
Pri izpolnjevanju praznih prostorov mora vsaka vrstica, stolpec in podmreža 3x3 vsebovati vse števke od 1 do 9.
Preprost skript Python vam lahko pomaga rešiti uganko Sudoku. Analizira lahko vse prazne prostore na tabli Sudoku in poišče možno število za zapolnitev vsakega praznega prostora.
Kako ustvariti in prikazati tablo za sudoku
Znotraj skripta Python boste morali uporabiti seznam nizov za shranjevanje vrednosti nerešene uganke Sudoku.
Koda, uporabljena v tem projektu, je na voljo tukaj GitHub repo pod licenco MIT.
- Znotraj novega skripta Python, imenovanega sudoku.py, shranite vse vrednosti za mrežo 9x9. Vsaka vrstica in stolpec predstavlja devet števil čez in navzdol po uganki Sudoku. Dodajte 0, da predstavljate prostore, ki jih je treba rešiti:
tabla = [
[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]
] - Znotraj nove funkcije, imenovane print_board, uporabite zanko for za obdelavo vsake vrstice v mreži:
deftiskalna_plošča(tabla):
za vrstica v obseg (9): - Če želite vsako vrstico razdeliti na tretjine, preverite, ali je vrstica deljiva s tri, in dodajte črto:
če vrstica % 3 == 0in vrstica != 0:
natisni("- - - - - - - - - - - - - - ") - Znotraj vsake vrstice pojdite skozi vsak stolpec. Stolpce lahko razdelite tudi na tretjine, tako da preverite, ali je stolpec deljiv s tri:
za col v obseg (9):
če stolpec % 3 == 0in col != 0:
natisni(" | ", konec="") - Natisnite vrednost števila, shranjeno v mreži. Če je stolpec zadnji stolpec za določeno vrstico, dodajte prelomno vrstico, tako da se naslednja vrstica pojavi v novi vrstici:
če col == 8:
natisni (tabla[vrstica][col])
drugače:
print (str (board[row][col]) + " ", konec="") - Pokličite funkcijo za tiskanje plošče:
print_board (tabla) - V ukazni vrstici se pomaknite do mape, v kateri ste shranili skript python, na primer:
cd namizje - Za zagon skripta Sudoku uporabite ukaz python. Oglejte si uganko, natisnjeno na zaslonu:
python sudoku.py
Kako prepoznati prazne prostore za rešitev
Lahko se premikate po seznamih in poiščete presledke, ki so sestavljeni iz ničel. Ti določajo, katere prostore je treba rešiti.
- V novi funkciji, imenovani find_empty(), preglejte vsako vrstico in stolpec na tabli:
defnajdi_prazno(tabla):
za vrstica v obseg (9):
za col v obseg (9): - Če je vrednost trenutne celice 0, vrne trenutni položaj prazne celice:
če tabla[vrstica][col] == 0:
vrnitev (vrstica, stolpec) - Če skript doseže konec funkcije, to pomeni, da skript ni našel nobene celice z vrednostjo 0. V tem primeru ne vrnite ničesar:
vrnitevNoben - V novi funkciji, imenovani solve(), uporabite funkcijo find, da poiščete prvi prazen prostor na tabli:
defrešiti(tabla):
najdi = najdi_prazno (tabla) - Funkcija find_empty() vrne položaj celice v obliki tuple, na primer (0, 2). Te vrednosti shranite ločeno v vrstica in col spremenljivke. V nasprotnem primeru vrnite true, da označite, da ni več praznih prostorov za rešitev:
čene najti:
vrnitevPrav
drugače:
vrstica, stolpec = najdi
Kako rešiti uganko za vsako vrstico, stolpec in mrežo 3x3
Zdaj, ko lahko identificirate prvi prazen prostor, ki ga želite rešiti, boste morali poskusiti najti ustrezno številko, da zapolnite ta prostor in rešite uganko.
Uporaba rekurzije, pokličite funkcijo solve() v sebi, da preizkusite vse možne kombinacije vrednosti tudi za vse druge prostore.
- Znotraj funkcije solve() se po iskanju prvega praznega prostora pomikajte po posameznih številkah od 1 do 9. Te številke predstavljajo možne številke, ki bi lahko zapolnile nerešen prostor:
za št v obseg (1, 10): - V novo funkcijo vnesite tablo, možno število in položaj prazne celice. Nova funkcija bo vrnila true, če je to število veljavno število, ki lahko reši ta prazen prostor. Če je veljavna, dodelite to številko celici na tabli:
če je_veljaven (tabla, št., (vrstica, stolpec)):
tabla[vrstica][kol] = št - Ustvarite funkcijo is_valid() z ustreznimi parametri:
defje_veljaven(tabla, št., poz.): - S funkcijo preverite, ali postavitev številke na ta položaj krši katera koli pravila igre sudoku. Najprej preverite, ali ta številka že obstaja v vrstici ali stolpcu celice:
za col v obseg (9):
če tabla [pos [0]][col] == št in pos [1] != col:
vrnitevFalseza vrstica v obseg (9):
če tabla[vrstica][pos[1]] == št in pos [0] != vrstica:
vrnitevFalse - Pridobite mrežo 3x3, ki ji celica pripada. To lahko storite tako, da položaj celice delite s tri:
box_row = pos[0] // 3
box_col = pos[1] // 3 - Za vsako vrstico in stolpec v tej mreži 3x3 preverite, ali številka že obstaja. Če se, vrni false:
za vrstica v obseg (box_row*3, box_row*3 + 3):
za col v obseg (box_col*3, box_col*3 + 3):
če tabla[vrstica][kol] == št in (vrstica, stolpec) != pos:
vrnitevFalse - Če skript doseže konec funkcije, to pomeni, da nobeno od pravil sudokuja ni uspelo. Vrni resnico:
vrnitevPrav - Funkcija is_valid() samo preveri, ali je postavitev številke veljavna, vendar to ne pomeni, da je pravilen odgovor na splošno rešitev. Znotraj funkcije solve() ponovno pokličite funkcijo solve() s posodobljeno tablo. Funkcija solve() lahko doseže stanje, ko ne more več uporabljati nobenih številk za zapolnjevanje presledkov. V tem primeru celotna funkcija vrne false, ponastavi določeno celico nazaj na 0 in se vrne nazaj. Funkcija solve() vrne true le, če lahko skript zapolni vse presledke:
za št v obseg (1, 10):
če je_veljaven (tabla, št., (vrstica, stolpec)):
tabla[vrstica][kol] = št
če reši (tabla):
vrnitevPrav
tabla[vrstica][col] = 0vrnitevFalse - Če želite začeti reševati uganko, pokličite funkcijo solve() z izvirno ploščo na dnu skripta, potem ko ste deklarirali funkcijo solve():
reši (tabla) - Natisnite končni rezultat:
natisni("Rešeno:")
print_board (tabla) - V ukazni vrstici uporabite ukaz python, da znova zaženete skript. Oglejte si rešeno uganko, natisnjeno na zaslonu:
python sudoku.py
Ustvarjanje iger z uporabo Pythona
Sudoku je le ena od mnogih iger, ki jih lahko ustvarite in rešite s Pythonom. Python lahko uporabite za ustvarjanje različnih drugih iger, kot je mešanje besed, besedilna pustolovska igra ali barvna igra, če naštejemo le nekatere.
