Studer denne kode omhyggeligt, og opdag en smart måde at bruge rekursion til at løse de vanskelige sudoku-gåder.
Sudoku er et populært talpuslespil, der består af et 9x9 gitter med cifre fra 1 til 9. Puslespillet indeholder en kombination af tal og nogle tomme felter, som du skal udfylde.
Når du udfylder de tomme pladser, skal hver række, kolonne og 3x3 undergitter indeholde alle cifre fra 1 til 9.
Et simpelt Python-script kan hjælpe med at løse et Sudoku-puslespil for dig. Den kan analysere alle de tomme pladser på Sudoku-brættet, og finde et muligt tal at udfylde hver tom plads.
Sådan oprettes og vises Sudoku-brættet
Inde i et Python-script skal du bruge en liste over arrays til at gemme værdierne af det uløste Sudoku-puslespil.
Koden brugt i dette projekt er tilgængelig i dette GitHub repo under MIT-licensen.
- Gem alle værdierne for 9x9-gitteret i et nyt Python-script kaldet sudoku.py. Hver række og kolonne repræsenterer de ni tal på tværs og ned ad Sudoku-puslespillet. Tilføj 0'er for at repræsentere de rum, der skal løses:
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]
] - Inde i en ny funktion kaldet print_board, brug en for loop for at behandle hver række i gitteret:
defprint_board(bestyrelse):
til række i rækkevidde(9): - For at adskille hver række i tredjedele skal du kontrollere, om rækken er delelig med tre, og tilføje en linje:
hvis række % 3 == 0og række != 0:
Print("- - - - - - - - - - - - - - ") - Inden for hver række, løkke gennem hver kolonne. Du kan også opdele kolonner i tredjedele ved at kontrollere, om kolonnen er delelig med tre:
til col i rækkevidde(9):
hvis col % 3 == 0og col != 0:
Print(" | ", ende="") - Udskriv den talværdi, der er gemt i gitteret. Hvis kolonnen er den sidste kolonne for den pågældende række, skal du tilføje en brudlinje, så følgende række vises på en ny linje:
hvis col == 8:
print (tavle[række][kol])
andet:
print (str (bræt[række][kol]) + " ", ende="") - Kald funktionen til at printe tavlen:
print_board (board) - På en kommandolinje skal du navigere til den mappe, hvor du gemte dit python-script, for eksempel:
cd skrivebord - Brug python-kommandoen til at køre dit Sudoku-script. Se puslespillet printet på skærmen:
python sudoku.py
Sådan identificerer du de tomme rum, der skal løses
Du kan gå gennem listerne for at finde de mellemrum, der består af 0'er. Disse bestemmer, hvilke rum der skal løses.
- I en ny funktion kaldet find_empty(), løkke gennem hver række og kolonne på tavlen:
deffind_tom(bestyrelse):
til række i rækkevidde(9):
til col i rækkevidde(9): - Hvis værdien af den aktuelle celle er 0, returner den aktuelle position for den tomme celle:
hvis board[række][col] == 0:
Vend tilbage (række, kolonne) - Hvis scriptet når slutningen af funktionen, betyder det, at scriptet ikke kunne finde nogen celler med værdien 0. I dette tilfælde skal du ikke returnere noget:
Vend tilbageIngen - I en ny funktion kaldet solve(), brug find-funktionen til at finde den første tomme plads på brættet:
defløse(bestyrelse):
find = find_tom (bræt) - Find_empty()-funktionen returnerer cellepositionen i tupelformat, for eksempel (0, 2). Gem disse værdier separat i række og col variabler. Ellers skal du returnere sand for at angive, at der ikke er tomme pladser tilbage at løse:
hvisikke Find:
Vend tilbageRigtigt
andet:
række, col = find
Sådan løses puslespillet for hver række, kolonne og 3x3 gitter
Nu hvor du kan identificere den første tomme plads, du skal løse, bliver du nødt til at prøve at finde et passende tal til at udfylde den plads og løse gåden.
Brug af rekursion, kalder solve()-funktionen i sig selv for også at prøve enhver mulig kombination af værdier for alle de andre rum.
- Inde i solve()-funktionen, efter at have fundet det første tomme rum, skal du gå gennem hvert tal fra 1 til 9. Disse tal repræsenterer de mulige tal, der kunne fylde det uløste rum:
til num i rækkevidde(1, 10): - Indtast tavlen, det mulige nummer og positionen af den tomme celle i en ny funktion. Den nye funktion vil returnere sand, hvis det tal er et gyldigt tal, der kan løse det tomme felt. Hvis det er gyldigt, tildel det nummer til cellen på tavlen:
hvis is_valid (board, num, (row, col)):
bord[række][kol] = antal - Opret funktionen is_valid() med matchende parametre:
defer gyldig(tavle, antal, pos): - Brug funktionen til at kontrollere, om placeringen af tallet i den position overtræder nogen af reglerne i Sudoku-spillet. Først skal du kontrollere, om dette nummer allerede findes i rækken eller kolonnen i cellen:
til col i rækkevidde(9):
hvis bestyrelse[pos[0]][col] == antal og pos[1] != col:
Vend tilbageFalsktil række i rækkevidde(9):
hvis tavle[række][pos[1]] == antal og pos[0] != række:
Vend tilbageFalsk - Få det 3x3-gitter, som cellen tilhører. Du kan gøre dette ved at dividere cellens position med tre:
box_row = pos[0] // 3
box_col = pos[1] // 3 - For hver række og kolonne i det 3x3-gitter skal du kontrollere, om nummeret allerede findes. Hvis det gør det, returner false:
til række i interval (kasse_række*3, box_row*3 + 3):
til col i interval (box_col*3, box_col*3 + 3):
hvis bord[række][kol] == antal og (række, kolonne) != pos:
Vend tilbageFalsk - Hvis scriptet når slutningen af funktionen, betyder det, at ingen af Sudoku-reglerne mislykkedes. Returner sand:
Vend tilbageRigtigt - Funktionen is_valid() kontrollerer kun, om nummerplaceringen er gyldig, men det betyder ikke, at det er det rigtige svar på den overordnede løsning. Inden for solve()-funktionen skal du kalde solve()-funktionen igen med det opdaterede bord. solve()-funktionen kan nå en tilstand, hvor den ikke længere kan bruge nogen tal til at udfylde mellemrum. I dette tilfælde returnerer hele funktionen falsk, nulstiller den pågældende celle tilbage til 0 og går tilbage. solve()-funktionen returnerer kun sand, når scriptet kan udfylde alle mellemrum:
til num i rækkevidde(1, 10):
hvis is_valid (board, num, (row, col)):
bord[række][kol] = antal
hvis løse (bord):
Vend tilbageRigtigt
board[række][col] = 0Vend tilbageFalsk - For at begynde at løse gåden skal du kalde solve()-funktionen med den originale tavle, nederst i scriptet, efter at have erklæret solve()-funktionen:
løse (bord) - Print det endelige resultat:
Print("Løst:")
print_board (board) - På kommandolinjen skal du bruge python-kommandoen til at køre scriptet igen. Se det løste puslespil trykt på skærmen:
python sudoku.py
Oprettelse af spil ved hjælp af Python
Sudoku er blot et af de mange spil, du kan oprette og løse ved hjælp af Python. Du kan bruge Python til at skabe forskellige andre spil, såsom et ordvirvar, et tekstbaseret eventyrspil eller et farvespil, for blot at nævne nogle få.
