Pažljivo proučite ovaj kod i otkrijte pametan način korištenja rekurzije za rješavanje tih lukavih sudoku zagonetki.
Sudoku je popularna slagalica brojeva koja se sastoji od mreže 9x9 sa znamenkama od 1 do 9. Slagalica uključuje kombinaciju brojeva i nekoliko praznih mjesta koja trebate popuniti.
Prilikom popunjavanja praznih mjesta, svaki redak, stupac i podmreža 3x3 trebaju sadržavati sve znamenke od 1 do 9.
Jednostavna Python skripta može vam pomoći u rješavanju Sudoku zagonetke. Može analizirati sva prazna mjesta na Sudoku ploči i pronaći mogući broj za popunjavanje svakog praznog mjesta.
Kako izraditi i prikazati Sudoku ploču
Unutar Python skripte morat ćete upotrijebiti popis nizova za pohranjivanje vrijednosti neriješene Sudoku zagonetke.
Kod korišten u ovom projektu dostupan je u ovom GitHub repo pod licencom MIT-a.
- Unutar nove Python skripte pod nazivom sudoku.py, pohranite sve vrijednosti za mrežu 9x9. Svaki redak i stupac predstavljaju devet brojeva duž Sudoku slagalice. Dodajte 0 za predstavljanje prostora koje treba riješiti:
ploča = [
[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]
] - Unutar nove funkcije pod nazivom print_board, koristite for petlju za obradu svakog reda u mreži:
deftiskana_ploča(odbor):
za red u raspon (9): - Da biste svaki red podijelili na trećine, provjerite je li red djeljiv s tri i dodajte redak:
ako red % 3 == 0i red != 0:
ispis("- - - - - - - - - - - - - - ") - Unutar svakog retka, prođite kroz svaki stupac. Također možete podijeliti stupce na trećine tako da provjerite je li stupac djeljiv s tri:
za kol u raspon (9):
ako stupac % 3 == 0i stupac != 0:
ispis(" | ", kraj="") - Ispišite vrijednost broja pohranjenu u mreži. Ako je stupac posljednji stupac za taj određeni redak, dodajte prijelomni redak tako da se sljedeći redak pojavi u novom retku:
ako stupac == 8:
ispis (ploča[red][kol])
drugo:
ispis (str (ploča[red][kol]) + " ", kraj="") - Pozovite funkciju za ispis ploče:
print_board (ploča) - U naredbenom retku idite do mape u koju ste pohranili svoju python skriptu, na primjer:
cd radna površina - Upotrijebite naredbu python za pokretanje Sudoku skripte. Pogledaj zagonetku ispisanu na ekranu:
python sudoku.py
Kako identificirati prazna mjesta za rješavanje
Možete proći kroz popise kako biste pronašli razmake koji se sastoje od nula. Oni određuju koje prostore je potrebno riješiti.
- U novoj funkciji koja se zove find_empty(), prođite kroz svaki redak i stupac na ploči:
defpronaći_prazno(odbor):
za red u raspon (9):
za kol u raspon (9): - Ako je vrijednost trenutne ćelije 0, vrati trenutni položaj prazne ćelije:
ako ploča[red][kol] == 0:
povratak (redak, stupac) - Ako skripta dođe do kraja funkcije, to znači da skripta nije mogla pronaći nijednu ćeliju s vrijednošću 0. U ovom slučaju ne vraćajte ništa:
povratakNijedan - U novoj funkciji koja se zove solve(), upotrijebite funkciju find za pronalaženje prvog praznog mjesta na ploči:
defriješiti(odbor):
pronaći = find_empty (ploča) - Funkcija find_empty() vraća položaj ćelije u formatu torke, na primjer (0, 2). Spremite ove vrijednosti odvojeno u red i kol varijable. U suprotnom vratite true da označite da nema praznih mjesta za rješavanje:
akone pronaći:
povratakPravi
drugo:
redak, stupac = pronađi
Kako riješiti zagonetku za svaki redak, stupac i mrežu 3x3
Sada kada možete identificirati prvi prazan prostor za rješavanje, morat ćete pokušati pronaći odgovarajući broj da ispunite taj prostor i riješite zagonetku.
Korištenje rekurzije, pozovite funkciju solve() unutar sebe kako biste isprobali sve moguće kombinacije vrijednosti i za sve ostale prostore.
- Unutar funkcije solve(), nakon pronalaska prvog praznog mjesta, prođite kroz svaki broj od 1 do 9. Ovi brojevi predstavljaju moguće brojeve koji bi mogli ispuniti neriješeni prostor:
za br u raspon (1, 10): - Unesite ploču, mogući broj i položaj prazne ćelije u novu funkciju. Nova funkcija vratit će true ako je taj broj važeći broj koji može riješiti taj prazan prostor. Ako je valjan, dodijelite taj broj ćeliji na ploči:
ako is_valja (ploča, broj, (red, stupac)):
ploča[red][kol] = br - Stvorite funkciju is_valid() s odgovarajućim parametrima:
defje_važeći(ploča, broj, pos): - Pomoću ove funkcije provjerite krši li postavljanje broja na tu poziciju neka pravila Sudoku igre. Prvo provjerite postoji li taj broj već u retku ili stupcu ćelije:
za kol u raspon (9):
ako ploča[pos[0]][col] == br i pos [1] != stupac:
povrataklažnoza red u raspon (9):
ako ploča[red][poz[1]] == br i pos [0] != red:
povrataklažno - Nabavite mrežu 3x3 kojoj ćelija pripada. To možete učiniti dijeljenjem položaja ćelije s tri:
box_row = pos[0] // 3
box_col = pos[1] // 3 - Za svaki redak i stupac u toj mreži 3x3 provjerite postoji li broj već. Ako ima, vrati false:
za red u raspon (box_row*3, box_row*3 + 3):
za kol u raspon (box_col*3, box_col*3 + 3):
ako ploča[red][kol] == br i (redak, stupac) != pos:
povrataklažno - Ako skripta dođe do kraja funkcije, to znači da nijedno Sudoku pravilo nije uspjelo. Vrati točno:
povratakPravi - Funkcija is_valid() samo provjerava je li položaj broja valjan, ali to ne znači da je to točan odgovor na cjelokupno rješenje. Unutar funkcije solve(), ponovno pozovite funkciju solve() s ažuriranom pločom. Funkcija solve() može doći u stanje u kojem više ne može koristiti brojeve za popunjavanje razmaka. U ovom slučaju cijela funkcija vraća false, resetira tu ćeliju natrag na 0 i vraća se unatrag. Funkcija solve() vraća vrijednost true samo ako skripta može popuniti sva mjesta:
za br u raspon (1, 10):
ako is_valja (ploča, broj, (red, stupac)):
ploča[red][kol] = br
ako riješiti (ploča):
povratakPravi
ploča[red][kol] = 0povrataklažno - Da biste započeli rješavati zagonetku, pozovite funkciju solve() s originalnom pločom, na dnu skripte, nakon deklaracije funkcije solve():
riješiti (ploča) - Ispiši konačni rezultat:
ispis("Riješeno:")
print_board (ploča) - U naredbenom retku upotrijebite naredbu python za ponovno pokretanje skripte. Pogledajte riješenu zagonetku ispisanu na ekranu:
python sudoku.py
Stvaranje igara pomoću Pythona
Sudoku je samo jedna od mnogih igara koje možete kreirati i riješiti pomoću Pythona. Možete koristiti Python za stvaranje raznih drugih igara, kao što je zbrka riječi, tekstualna avanturistička igra ili igra boja, da spomenemo samo neke.
