Uurige seda koodi hoolikalt ja avastage nutikas viis nende keeruliste sudokumõistatuste lahendamiseks kasutada rekursiooni.

Sudoku on populaarne numbrimõistatus, mis koosneb 9x9 ruudustikust numbritega 1 kuni 9. Pusle sisaldab numbrite kombinatsiooni ja mõningaid tühikuid, mille peate täitma.

Tühjade kohtade täitmisel peab iga rida, veerg ja 3x3 alamruudustik sisaldama kõiki numbreid vahemikus 1 kuni 9.

Lihtne Pythoni skript võib aidata lahendada Sudoku mõistatuse. See suudab analüüsida kõiki Sudoku tahvli tühje kohti ja leida iga tühja koha täitmiseks võimaliku numbri.

Kuidas luua ja kuvada Sudoku tahvlit

Pythoni skriptis peate kasutama massiivide loendit, et salvestada lahendamata Sudoku mõistatuse väärtused.

Selles projektis kasutatav kood on saadaval selles GitHubi repo MIT litsentsi alusel.

  1. Salvestage uude Pythoni skripti nimega sudoku.py kõik 9x9 ruudustiku väärtused. Iga rida ja veerg tähistavad üheksat numbrit üle ja alla Sudoku pusle. Lahendamist vajavate ruumide tähistamiseks lisage nullid: 
    tahvel = [
     [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]
    ]
  2. Uues funktsioonis print_board kasutage for-silmust ruudustiku iga rea ​​töötlemiseks:
    defprint_board(laud):
    jaoks rida sisse vahemik(9):
  3. Iga rea ​​kolmandikuks eraldamiseks kontrollige, kas rida jagub kolmega, ja lisage rida:
    kui rida % 3 == 0ja rida != 0:
     print("- - - - - - - - - - - - - - ")
  4. Sirvige igas reas läbi iga veeru. Samuti saate veerud kolmandikuks jagada, kontrollides, kas veerg jagub kolmega:
    jaoks kol sisse vahemik(9):
    kui veeru % 3 == 0ja veerg != 0:
     print(" | ", lõpp="")
  5. Printige ruudustikule salvestatud numbriväärtus. Kui veerg on selle konkreetse rea viimane veerg, lisage katkestusjoon, et järgmine rida ilmuks uuele reale:
    kui veerg == 8:
     print (tahvel[rida][kolg])
    muidu:
     print (str (tahvel[rida][col]) + " ", lõpp="")
  6. Helistage tahvli printimise funktsioonile:
    print_board (tahvel)
  7. Liikuge käsureal kausta, kuhu salvestasite oma pythoni skripti, näiteks:
    cd töölaud
  8. Kasutage Sudoku skripti käivitamiseks käsku python. Vaadake ekraanile prinditud puslet:
    python sudoku.py

Kuidas tuvastada tühje kohti, mida lahendada

0-dest koosnevate tühikute leidmiseks saate loendeid läbida. Need määravad, millised ruumid vajavad lahendamist.

  1. Uues funktsioonis nimega find_empty() sirvige tahvli iga rida ja veerg:
    defleia_tühi(laud):
    jaoks rida sisse vahemik(9):
    jaoks kol sisse vahemik(9):
  2. Kui praeguse lahtri väärtus on 0, tagastage tühja lahtri praegune asukoht:
    kui tahvel[rida][kolon] == 0:
    tagasi (rida, veerg)
  3. Kui skript jõuab funktsiooni lõpuni, tähendab see, et skript ei leidnud ühtegi lahtrit väärtusega 0. Sel juhul ärge tagastage midagi:
    tagasiMitte ühtegi
  4. Uues funktsioonis solve() kasutage laua esimese tühja koha leidmiseks funktsiooni find:
    deflahendada(laud):
     leia = leia_tühi (tahvel)
  5. Funktsioon find_empty() tagastab lahtri asukoha korteeživormingus, näiteks (0, 2). Salvestage need väärtused eraldi kausta rida ja kol muutujad. Vastasel juhul tagastage tõene, mis tähendab, et lahendamiseks pole jäänud tühje kohti:
    kuimitte leia:
    tagasiTõsi
    muidu:
     rida, veerg = leia

Kuidas lahendada iga rea, veeru ja 3x3 ruudustiku mõistatus

Nüüd, kui saate tuvastada esimese tühja ruumi, mida tuleb lahendada, peate proovima leida sobiva numbri selle ruumi täitmiseks ja mõistatuse lahendamiseks.

Rekursiooni kasutamine, kutsuge enda sees funktsioon solve(), et proovida kõiki võimalikke väärtuste kombinatsioone ka kõigi teiste ruumide jaoks.

  1. Funktsiooni solve() sees liikuge pärast esimese tühja ruumi leidmist läbi iga numbri vahemikus 1 kuni 9. Need numbrid tähistavad võimalikke numbreid, mis võivad täita lahendamata ruumi:
    jaoks nr sisse vahemik(1, 10):
  2. Sisestage tahvel, võimalik number ja tühja lahtri asukoht uude funktsiooni. Uus funktsioon tagastab tõene, kui see arv on kehtiv arv, mis suudab selle tühja ruumi lahendada. Kui see on kehtiv, määrake see number tahvli lahtrile:
    kui is_valid (tahvel, arv, (rida, veerg)):
     tahvel[rida][veerg] = arv
  3. Looge funktsioon is_valid() sobivate parameetritega:
    defon kehtiv(tahvel, number, pos):
  4. Kasutage funktsiooni, et kontrollida, kas numbri paigutamine sellesse kohta rikub Sudoku mängu reegleid. Esiteks kontrollige, kas see number on lahtri real või veerus juba olemas:
    jaoks kol sisse vahemik(9):
    kui laud[pos[0]][veerg] == num ja pos[1] != veerg:
    tagasiVale
    jaoks rida sisse vahemik(9):
    kui board[row][pos[1]] == num ja pos[0] != rida:
    tagasiVale
  5. Hankige 3x3 ruudustik, kuhu lahter kuulub. Seda saate teha, jagades lahtri asukoha kolmega:
     kasti_rida = pos[0] // 3
     box_col = pos[1] // 3
  6. Kontrollige selle 3x3 ruudustiku iga rea ​​ja veeru puhul, kas number on juba olemas. Kui jah, tagastage vale:
    jaoks rida sisse vahemik (kasti_rida*3, kasti_rida*3 + 3):
    jaoks kol sisse vahemik (kasti_kolb*3, box_col*3 + 3):
    kui tahvel[rida][veerg] == num ja (rida, veerg) != pos:
    tagasiVale
  7. Kui skript jõuab funktsiooni lõpuni, tähendab see, et ükski Sudoku reeglitest ei ebaõnnestunud. Tagasta tõene:
    tagasiTõsi
  8. Funktsioon is_valid() kontrollib ainult seda, kas numbripaigutus on kehtiv, kuid see ei tähenda, et see oleks õige vastus üldisele lahendusele. Funktsiooni solve() sees kutsuge uuendatud tahvliga uuesti funktsioon solve(). Funktsioon solve() võib jõuda olekusse, kus ta ei saa enam tühikute täitmiseks kasutada numbreid. Sel juhul tagastab kogu funktsioon vale, lähtestab selle konkreetse lahtri väärtuseks 0 ja liigub tagasi. Funktsioon solve() tagastab tõene ainult siis, kui skript suudab täita kõik tühikud:
    jaoks nr sisse vahemik(1, 10):
    kui is_valid (tahvel, arv, (rida, veerg)):
     tahvel[rida][veerg] = arv

    kui lahenda (laud):
    tagasiTõsi

     tahvel[rida][veerg] = 0
    tagasiVale
  9. Mõistatuse lahendamise alustamiseks kutsuge skripti allosas pärast funktsiooni solve() deklareerimist algse tahvliga funktsioon solve().
    lahendama (tahvel)
  10. Printige lõpptulemus:
    print("Lahendatud:")
    print_board (tahvel)
  11. Käsureal kasutage skripti uuesti käivitamiseks käsku python. Vaadake ekraanile prinditud lahendatud mõistatust:
    python sudoku.py

Mängude loomine Pythoni abil

Sudoku on vaid üks paljudest mängudest, mida saate Pythoni abil luua ja lahendada. Pythonit saate kasutada mitmesuguste muude mängude loomiseks, näiteks sõnade segamini, tekstipõhise seiklusmängu või värvimängu, kui nimetada vaid mõnda.