Studiați acest cod cu atenție și descoperiți o modalitate inteligentă de a folosi recursiunea pentru a rezolva acele puzzle-uri sudoku dificile.
Sudoku este un puzzle cu numere popular care constă dintr-o grilă 9x9 cu cifre de la 1 la 9. Puzzle-ul include o combinație de numere și câteva spații goale, pe care trebuie să le umpleți.
Când completați spațiile goale, fiecare rând, coloană și subgrilă 3x3 ar trebui să conțină toate cifrele de la 1 la 9.
Un simplu script Python poate ajuta la rezolvarea unui puzzle Sudoku pentru tine. Poate analiza toate spațiile goale de pe tabla Sudoku și poate găsi un număr posibil de completat în fiecare spațiu liber.
Cum să creați și să afișați placa Sudoku
În interiorul unui script Python, va trebui să utilizați o listă de matrice pentru a stoca valorile puzzle-ului Sudoku nerezolvat.
Codul folosit în acest proiect este disponibil în acesta Repoziție GitHub sub licența MIT.
- În interiorul unui nou script Python numit sudoku.py, stocați toate valorile pentru grila 9x9. Fiecare rând și coloană reprezintă cele nouă numere de-a lungul și de jos a puzzle-ului Sudoku. Adăugați 0 pentru a reprezenta spațiile care trebuie rezolvate:
bord = [
[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]
] - În interiorul unei noi funcții numite print_board, utilizați o buclă for pentru a procesa fiecare rând din grilă:
defprint_board(bord):
pentru rând în gamă(9): - Pentru a separa fiecare rând în treimi, verificați dacă rândul este divizibil cu trei și adăugați o linie:
dacă rând % 3 == 0și rând != 0:
imprimare("- - - - - - - - - - - - - - ") - În fiecare rând, treceți în buclă prin fiecare coloană. De asemenea, puteți împărți coloanele în treimi verificând dacă coloana este divizibilă cu trei:
pentru col în gamă(9):
dacă col % 3 == 0și col != 0:
imprimare(" | ", sfârşitul="") - Tipăriți valoarea numărului stocată în grilă. Dacă coloana este ultima coloană pentru acel rând, adăugați o linie de întrerupere, astfel încât următorul rând să apară pe o linie nouă:
dacă col == 8:
imprimare (planșă[rând][col])
altfel:
imprimare (str (board[rând][col]) + " ", sfârşitul="") - Apelați funcția pentru a imprima placa:
print_board (board) - Într-o linie de comandă, navigați la folderul în care ați stocat scriptul Python, de exemplu:
cd Desktop - Utilizați comanda python pentru a rula scriptul Sudoku. Vizualizați puzzle-ul imprimat pe ecran:
python sudoku.py
Cum să identifici spațiile goale de rezolvat
Puteți parcurge listele pentru a găsi spațiile care constau din 0. Acestea determină ce spații trebuie rezolvate.
- Într-o nouă funcție numită find_empty(), parcurgeți fiecare rând și coloană de pe tablă:
defgăsi_gol(bord):
pentru rând în gamă(9):
pentru col în gamă(9): - Dacă valoarea celulei curente este 0, returnați poziția curentă a celulei goale:
dacă bord[rând][col] == 0:
întoarcere (rând, col) - Dacă scriptul ajunge la sfârșitul funcției, înseamnă că scriptul nu a putut găsi nicio celulă cu valoarea 0. În acest caz, nu returnați nimic:
întoarcereNici unul - Într-o nouă funcție numită solve(), utilizați funcția find pentru a găsi primul spațiu gol de pe tablă:
defrezolva(bord):
găsi = găsi_gol (board) - Funcția find_empty() returnează poziția celulei în format tuplu, de exemplu, (0, 2). Salvați aceste valori separat în rând și col variabile. În caz contrar, returnați adevărat pentru a semnifica că nu mai sunt spații goale de rezolvat:
dacănu găsi:
întoarcereAdevărat
altfel:
rând, col = găsi
Cum să rezolvi puzzle-ul pentru fiecare rând, coloană și grilă 3x3
Acum că puteți identifica primul spațiu gol de rezolvat, va trebui să încercați să găsiți un număr potrivit pentru a umple acel spațiu și a rezolva puzzle-ul.
Folosind recursiunea, apelați funcția solve() în sine pentru a încerca orice combinație posibilă de valori și pentru toate celelalte spații.
- În interiorul funcției solve(), după ce ați găsit primul spațiu gol, treceți în buclă prin fiecare număr de la 1 la 9. Aceste numere reprezintă numerele posibile care ar putea umple spațiul nerezolvat:
pentru num în gamă(1, 10): - Introduceți placa, numărul posibil și poziția celulei goale într-o nouă funcție. Noua funcție va returna true dacă acel număr este un număr valid care poate rezolva acel spațiu gol. Dacă este valid, atribuiți acel număr celulei de pe tablă:
dacă este_valid (board, num, (rând, col)):
board[rând][col] = num - Creați funcția is_valid(), cu parametrii potriviți:
defeste valabil(board, num, pos): - Utilizați funcția pentru a verifica dacă plasarea numărului în acea poziție încalcă regulile jocului Sudoku. Mai întâi, verificați dacă acel număr există deja în rândul sau coloana celulei:
pentru col în gamă(9):
dacă bord[poz[0]][col] == num și pos[1] != col:
întoarcereFalspentru rând în gamă(9):
dacă bord[rând][poziție[1]] == num și pos[0] != rând:
întoarcereFals - Obțineți grila 3x3 căreia îi aparține celula. Puteți face acest lucru împărțind poziția celulei la trei:
box_row = pos[0] // 3
box_col = pos[1] // 3 - Pentru fiecare rând și coloană din acea grilă 3x3, verificați dacă numărul există deja. Dacă se întâmplă, returnați false:
pentru rând în interval (box_row*3, box_row*3 + 3):
pentru col în interval (box_col*3, box_col*3 + 3):
dacă bord[rând][col] == num și (rând, col) != poz:
întoarcereFals - Dacă scriptul ajunge la sfârșitul funcției, înseamnă că niciuna dintre regulile Sudoku nu a eșuat. Returnează adevărat:
întoarcereAdevărat - Funcția is_valid() verifică doar dacă plasarea numărului este validă, dar asta nu înseamnă că este răspunsul corect la soluția generală. În cadrul funcției solve(), apelați din nou funcția solve() cu placa actualizată. Funcția solve() poate ajunge într-o stare în care nu mai poate folosi niciun număr pentru a umple spații. În acest caz, întreaga funcție returnează false, resetează acea celulă particulară înapoi la 0 și dă înapoi. Funcția solve() returnează true numai atunci când scriptul poate umple toate spațiile:
pentru num în gamă(1, 10):
dacă este_valid (board, num, (rând, col)):
board[rând][col] = num
dacă rezolva (bord):
întoarcereAdevărat
bord[rând][col] = 0întoarcereFals - Pentru a începe rezolvarea puzzle-ului, apelați funcția solve() cu tabla originală, în partea de jos a scriptului, după declararea funcției solve():
rezolva (bord) - Imprimați rezultatul final:
imprimare("Rezolvat:")
print_board (board) - Pe linia de comandă, utilizați comanda python pentru a rula din nou scriptul. Vizualizați puzzle-ul rezolvat imprimat pe ecran:
python sudoku.py
Crearea de jocuri folosind Python
Sudoku este doar unul dintre numeroasele jocuri pe care le puteți crea și rezolva folosind Python. Puteți folosi Python pentru a crea diverse alte jocuri, cum ar fi un amestec de cuvinte, un joc de aventură bazat pe text sau un joc de culori, pentru a numi doar câteva.