Bestudeer deze code zorgvuldig en ontdek een slimme manier om recursie te gebruiken om die lastige sudoku-puzzels op te lossen.
Sudoku is een populaire cijferpuzzel die bestaat uit een raster van 9x9 met cijfers van 1 tot 9. De puzzel bevat een combinatie van cijfers en enkele lege ruimtes, die je moet invullen.
Bij het invullen van de lege ruimtes moet elke rij, kolom en 3x3 subraster alle cijfers van 1 tot en met 9 bevatten.
Een eenvoudig Python-script kan u helpen bij het oplossen van een Sudoku-puzzel. Het kan alle lege ruimtes op het Sudoku-bord analyseren en een mogelijk getal vinden om elke lege ruimte in te vullen.
Hoe het Sudoku-bord te maken en weer te geven
Binnen een Python-script moet je een lijst met arrays gebruiken om de waarden van de onopgeloste Sudoku-puzzel op te slaan.
De code die in dit project wordt gebruikt, is hierin beschikbaar GitHub-opslagplaats onder de MIT-licentie.
- Bewaar alle waarden voor het 9x9-raster in een nieuw Python-script genaamd sudoku.py. Elke rij en kolom vertegenwoordigt de negen getallen op en neer in de Sudoku-puzzel. Voeg nullen toe om de ruimtes weer te geven die moeten worden opgelost:
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]
] - Binnen een nieuwe functie genaamd print_board, gebruik een for-lus om elke rij in het raster te verwerken:
defprint_bord(bord):
voor rij in bereik(9): - Om elke rij in drieën te scheiden, controleert u of de rij deelbaar is door drie en voegt u een regel toe:
als rij % 3 == 0En rij!= 0:
afdrukken("- - - - - - - - - - - - - - ") - Loop binnen elke rij door elke kolom. U kunt kolommen ook in drieën splitsen door te controleren of de kolom deelbaar is door drie:
voor col in bereik(9):
als kleur % 3 == 0En col!= 0:
afdrukken(" | ", einde="") - Druk de nummerwaarde af die in het raster is opgeslagen. Als de kolom de laatste kolom is voor die specifieke rij, voegt u een breeklijn toe, zodat de volgende rij op een nieuwe regel verschijnt:
als col == 8:
print (bord[rij][col])
anders:
print (str (bord[rij][col]) + " ", einde="") - Roep de functie aan om het bord af te drukken:
afdrukbord (bord) - Navigeer in een opdrachtregel naar de map waarin u uw python-script hebt opgeslagen, bijvoorbeeld:
cd-bureaublad - Gebruik de opdracht python om uw Sudoku-script uit te voeren. Bekijk de puzzel die op het scherm is afgedrukt:
python sudoku.py
Hoe de lege ruimtes te identificeren die moeten worden opgelost
U kunt door de lijsten bladeren om de spaties te vinden die uit nullen bestaan. Deze bepalen welke ruimtes moesten worden opgelost.
- Loop in een nieuwe functie genaamd find_empty() door elke rij en kolom op het bord:
defvind_leeg(bord):
voor rij in bereik(9):
voor col in bereik(9): - Als de waarde van de huidige cel 0 is, geeft u de huidige positie van de lege cel terug:
als bord[rij][col] == 0:
opbrengst (rij, kolom) - Als het script het einde van de functie bereikt, betekent dit dat het script geen cellen met de waarde 0 kan vinden. Stuur in dit geval niets terug:
opbrengstGeen - Gebruik in een nieuwe functie genaamd solve() de functie find om de eerste lege ruimte op het bord te vinden:
defoplossen(bord):
vind = vind_leeg (bord) - De functie find_empty() retourneert de celpositie in tuple-indeling, bijvoorbeeld (0, 2). Sla deze waarden afzonderlijk op in het rij En col variabelen. Geef anders true terug om aan te geven dat er geen lege ruimtes meer zijn om op te lossen:
alsniet vinden:
opbrengstWAAR
anders:
rij, col = vinden
Hoe de puzzel op te lossen voor elke rij, kolom en 3x3 raster
Nu je de eerste lege ruimte kunt identificeren die moet worden opgelost, moet je proberen een geschikt getal te vinden om die ruimte te vullen en de puzzel op te lossen.
Recursie gebruiken, roep de functie solve() binnen zichzelf aan om elke mogelijke combinatie van waarden ook voor alle andere ruimten te proberen.
- Binnen de functie solve() loop je, na het vinden van de eerste lege ruimte, door elk getal van 1 tot 9. Deze getallen vertegenwoordigen de mogelijke getallen die de onopgeloste ruimte zouden kunnen vullen:
voor aantal in bereik(1, 10): - Voer het bord, het mogelijke nummer en de positie van de lege cel in een nieuwe functie in. De nieuwe functie retourneert true als dat getal een geldig getal is dat die lege ruimte kan oplossen. Als het geldig is, wijs dat nummer dan toe aan de cel op het bord:
als is_geldig (bord, num, (rij, kolom)):
bord[rij][kolom] = num - Maak de functie is_valid() met overeenkomende parameters:
defis geldig(bord, nummer, pos): - Gebruik de functie om te controleren of het plaatsen van het nummer op die positie in strijd is met de regels van het Sudoku-spel. Controleer eerst of dat nummer al bestaat in de rij of kolom van de cel:
voor col in bereik(9):
als bord[pos[0]][col] == num En pos[1] != col:
opbrengstValsvoor rij in bereik(9):
als bord[rij][positie[1]] == aantal En pos[0] != rij:
opbrengstVals - Verkrijg het 3x3 raster waartoe de cel behoort. U kunt dit doen door de positie van de cel door drie te delen:
box_row = pos[0] // 3
box_col = pos[1] // 3 - Controleer voor elke rij en kolom in dat 3x3-raster of het nummer al bestaat. Als dit het geval is, retourneert u false:
voor rij in bereik (box_row*3, box_row*3 + 3):
voor col in bereik (box_col*3, box_col*3 + 3):
als bord[rij][col] == num En (rij, kolom) != pos:
opbrengstVals - Als het script het einde van de functie bereikt, betekent dit dat geen van de Sudoku-regels is mislukt. Geef waar terug:
opbrengstWAAR - De functie is_valid() controleert alleen of de nummerplaatsing geldig is, maar dat betekent niet dat dit het juiste antwoord is op de algehele oplossing. Roep binnen de functie solve() opnieuw de functie solve() aan met het bijgewerkte bord. De functie solve() kan een toestand bereiken waarin geen getallen meer kunnen worden gebruikt om spaties in te vullen. In dit geval retourneert de hele functie false, zet die specifieke cel terug op 0 en gaat terug. De functie solve() retourneert alleen true als het script alle spaties kan vullen:
voor aantal in bereik(1, 10):
als is_geldig (bord, num, (rij, kolom)):
bord[rij][kolom] = num
als oplossen (bord):
opbrengstWAAR
bord[rij][col] = 0opbrengstVals - Om te beginnen met het oplossen van de puzzel, roep je de functie solve() aan met het originele bord, onderaan het script, nadat je de functie solve() hebt gedeclareerd:
oplossen (bord) - Druk het eindresultaat af:
afdrukken("Opgelost:")
afdrukbord (bord) - Gebruik op de opdrachtregel de opdracht python om het script opnieuw uit te voeren. Bekijk de opgeloste puzzel afgedrukt op het scherm:
python sudoku.py
Games maken met behulp van Python
Sudoku is slechts een van de vele spellen die je met Python kunt maken en oplossen. Je kunt Python gebruiken om verschillende andere spellen te maken, zoals een woord-jumble, een op tekst gebaseerd avonturenspel of een kleurenspel, om er maar een paar te noemen.