Az előző bejegyzésben mátrixok előállításáról és ezekkel kapcsolatos műveletek végző függvények készítéséről volt szó. Most alkalmazási példaként a sudoku játékot megoldó programot írunk. Bár a sudokut vélhetően mindenki ismeri, de a feladatspecifikációhoz most röviden összefoglaljuk.
A sudoku egy olyan logikai játék, melyben egy 9×9-es táblázat van 9 darab 3×3-as résztáblázatra felosztva, és minden résztáblázatot a nullánál nagyobb egyjegyű egész számokkal kell kitölteni úgy, hogy nem csak minden egyes résztáblázatban, hanem az egész 9×9-es táblázat minden egyes sorában és minden oszlopában az 1..9 számok mindegyike csak egyszer fordulhat elő. A játék egy olyan kezdőtáblázattal indul, amelyben bizonyos cellákban már szerepelnek számok. A feladat, hogy a maradék cellákat kell kitölteni az előbb írt feltételeknek megfelelően.
A sudoku programunkban a táblázatot mint mátrixot az előző bejegyzésben látottakhoz hasonlóan egy olyan listával modellezzük, amelyben a sorokat 9 darab 9 elemű lista képviseli.
A megoldás menete a következő lesz:
- Megkeressük a következő üres cellát a sudoku mátrixban. (Tehát azt, amelyben 0 érték szerepel)
- Ha nem találunk üres cellát, akkor meg van oldva a rejtvény, mert a következőkben ismertetett lépésekben mindig csak a szabályok szerint érvényes értéket írunk egy üres cellába.
- Ha találunk üres cellát, akkor megpróbáljuk egy megfelelő értékkel kitölteni.
- Ehhez vesszük sorban az 1..9 számokat.
- Ellenőrizzük, hogy az aktuális szám egy lehetséges, érvényes megoldás-e.
- Ha igen, azaz az aktuális szám egy érvényes szám, akkor az eddig üres cella értékét erre írjuk át.
- Most van egy egyetlen számban módosított sudoku mátrixunk. Erre kell a fenti lépéseket újra elvégezni, tehát folytatjuk az 1. lépéssel. Vagyis rekurzívan oldjuk meg a feladatot.
- Egy új lehetséges számmal próbálkozunk a 4. lépéshez visszatérve, ha
- az aktuális szám nem lehet érvényes érték, vagy
- a rekurzív lépésekben kiderül, hogy egy szám sem felel meg. Ekkor a korábban átírt cellát visszaállítjuk üresnek.
- Ha a 4. lépés számait sorra véve egyik sem bizonyul megfelelőnek, akkor a feladatnak nincs megoldása.
- A helyesen megoldott táblázatot megjelenítjük.
Látható, hogy az algoritmus elvi alapja, hogy próbálkozunk, aztán ha nem jön be, akkor ezt elvetjük, azaz visszalépünk és egy másik úton-módon keressük a megoldást. E jellege miatt ezt visszalépéses keresési (backtracking) algoritmusnak nevezik.
A sudoku megoldó program egy lehetséges változatát láthatjuk alább.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
from itertools import product def következő_üres_cella(sudoku_mátrix) -> tuple: """Megkeresi a következő üres (azaz 0 értékű) cellát. Ha van ilyen, akkor annak sor és oszlop indexével tér vissza. Ha nincs, akkor (None, None) lesz az eredmény.""" for si, oi in product(range(9), range(9)): if sudoku_mátrix[si][oi] == 0: return si, oi return None, None def az_érték_lehetséges(sudoku_mátrix, cella_érték, sor_index, oszlop_index) -> bool: """A visszatérési értéke True, ha a cella_érték a megadott sor- és oszlopindexek által meghatározott sudoku mátrix cellában egy lehetséges megoldás. """ # Ha a megadott indexű sorban vagy oszlopban az cella_érték már szerepel, akkor az nem lehet megfelelő. sor = sudoku_mátrix[sor_index] oszlop = [sudoku_mátrix[i][oszlop_index] for i in range(9)] if cella_érték in sor or cella_érték in oszlop: return False # Megkeressük, hogy az argumentumban megadott sor- és oszlopindexszel azonosított cella a 9 közül # melyik 3x3-as kis mátrixhoz tartozik. E mátrix bal felső sarkának sor- és oszlopindexét határozzuk meg. mx3x3_si = (sor_index // 3) * 3 mx3x3_oi = (oszlop_index // 3) * 3 # Ha az érték szerepel a 3x3-as kis mátrixban, akkor az nem lehet megfelelő. for si, oi in product(range(mx3x3_si, mx3x3_si + 3), range(mx3x3_oi, mx3x3_oi + 3)): if sudoku_mátrix[si][oi] == cella_érték: return False # Ha az értéket a megadott sor- és oszlopindexek által meghatározott sor, oszlop és # 3x3-as mátrix egyike sem tartalmazza, akkor az egy lehetséges megoldás. return True def sudoku_megoldás(sudoku_mátrix:list): """Sudoku játék megoldását végzi visszalépéses keresés algoritmussal. Az argumentum egy 9x9 elemet tartalmazó mátrix, ami egy olyan lista, amelynek sorai 9 elemű listák""" # Megkeressük a következő üres cellát a sudoku mátrixban. üres_cella_si, üres_cella_oi = következő_üres_cella(sudoku_mátrix) # Ha a keresés eredményeként kapott sor és oszlop értéke None, akkor az azt # jelenti, hogy nincs több üres cella, és egyben azt is, hogy megoldottuk a feladatot, mert # csak érvényes értékekkel töltöttük fel az üres helyeket. if üres_cella_si is None: return True # Ha van üres cella, akkor megpróbáljuk megfelelő értékkel kitölteni. # Ezért sorban, 1-től 9-ig vesszük a számokat. for lehetséges_érték in range(1, 10): # Ellenőrizzük, hogy az aktuális szám egy lehetséges, érvényes megoldás-e. if az_érték_lehetséges(sudoku_mátrix, lehetséges_érték, üres_cella_si, üres_cella_oi): # Ha igen, a szám egy lehetséges érvényes, akkor a cella értékét erre írjuk át. sudoku_mátrix[üres_cella_si][üres_cella_oi] = lehetséges_érték # Innentől kezdve az eljárás ugyanaz (üres cella keresése, szám érvényesség esetén cellaérték módosítás) # Ezért rekurzívan folytatjuk a módosított sudoku mátrixszal mindaddig, amíg van üres cella. if sudoku_megoldás(sudoku_mátrix): return True # Egy új lehetséges számmal próbálkozunk, ha az aktuális szám nem lehet érvényes érték, vagy # rekurzív lépésekben kiderül, hogy egy szám sem felel meg. Ez utóbbi esetén a korábban átírt cellát # visszaállítjuk üresnek. sudoku_mátrix[üres_cella_si][üres_cella_oi] = 0 return False def mátrix_string(mátrix: list[list]): sorok_száma, oszlopok_száma = len(mátrix), len(mátrix[0]) # 1. meghatározzuk az egyes oszlopok karakterekben mért maximális elemhosszait. max_számhosszok_oszlopokban = [max([len(str(e)) for e in o]) for o in zip(*mátrix)] # 2. Előállítjuk a mátrixot karakterlánc formában. # Az egyes sorok elemeit az adott oszlop max mezőszélességével formázzuk. mátrix_string = '' for si in range(sorok_száma): for oi in range(oszlopok_száma): mátrix_string += '|{:>{szélesség}}'.format(mátrix[si][oi], szélesség=max_számhosszok_oszlopokban[oi] + 2) mátrix_string += '|\n' return mátrix_string # TESZT # Sudoku sorok értékei egy folytonos karaktersorban. sudoku_sorok = '203610000580007000400080020802000007000305000600000402040070008000400071000061504' # A sudoku mátrix előállítása listaépítő kifejezéssel, amelyben a karaktersorozatot 9 hosszú részekre bontjuk, # és az elemeket int számokká konvertáljuk. sudoku = [[*map(int, sudoku_sorok[i: i + 9])] for i in range(0, len(sudoku_sorok), 9)] # A megoldandó sudoku mátrix megjelenítése. print('A megoldandó sudoku:') print(mátrix_string(sudoku)) # A rejtvény megoldása. sudoku_megoldás(sudoku) # A megoldott sudoku mátrix megjelenítése. print('A megoldás:') print(mátrix_string(sudoku)) # Eredmény: A megoldandó sudoku: | 2| 0| 3| 6| 1| 0| 0| 0| 0| | 5| 8| 0| 0| 0| 7| 0| 0| 0| | 4| 0| 0| 0| 8| 0| 0| 2| 0| | 8| 0| 2| 0| 0| 0| 0| 0| 7| | 0| 0| 0| 3| 0| 5| 0| 0| 0| | 6| 0| 0| 0| 0| 0| 4| 0| 2| | 0| 4| 0| 0| 7| 0| 0| 0| 8| | 0| 0| 0| 4| 0| 0| 0| 7| 1| | 0| 0| 0| 0| 6| 1| 5| 0| 4| A megoldás: | 2| 9| 3| 6| 1| 4| 7| 8| 5| | 5| 8| 6| 2| 3| 7| 1| 4| 9| | 4| 1| 7| 5| 8| 9| 6| 2| 3| | 8| 5| 2| 1| 4| 6| 3| 9| 7| | 9| 7| 4| 3| 2| 5| 8| 1| 6| | 6| 3| 1| 7| 9| 8| 4| 5| 2| | 1| 4| 5| 9| 7| 3| 2| 6| 8| | 3| 6| 8| 4| 5| 2| 9| 7| 1| | 7| 2| 9| 8| 6| 1| 5| 3| 4| |
Az első függvény a mátrixban megkeresi a következő 0 értékű cellát, és ha van, akkor annak sor- és oszlopindexével tér vissza. Ha ilyen nem található, akkor None értékeket tartalmazó tuple lesz az eredmény.
A második függvény ellenőrzi, hogy a sudoku szabályai szerint egy indexekkel megadott cellába a szintén argumentumként adott számérték megfelelő megoldás lehet-e. A függvény először a sorban, valamint az oszlopban való megfelelést vizsgálja. Ha ott nincs kizáró ok, akkor következik, hogy megnézzük, hogy abban a kis 3×3-as résztáblázatban, amelybe a cella beleesik szintén áll-e a megfelelőség.
E két függvényben a sor- és oszlopindexek iterálását egymásba ágyazott for-ciklusok helyett az itertools modul product() függvényével végezzük, ami talán egy kicsit jobban olvashatóvá teszi a kódot. Az egymásba ágyazott for-ciklusok lényegében az indexek Descartes-szorzatát képezik. Ugyanezt teszi a product() függvény is.
A harmadik függvény végzi a feladat megoldását a fent sorolt lépések szerint.
A kommentek mindhárom függvénynél segítik a megértést.
A tesztelés során egy karakterláncban kapjuk folytatólagosan a megoldandó táblázat sorértékeit, ahol a 0 jelenti a kitöltendő üres cellát.
Ebből egy korábbi bejegyzésben szereplő módon 9 karakter hosszú számsor darabokat készítünk és ezekből építjük fel a sudoku mátrixot. /Az, hogy a sorok számértékei kezdetben egy karakterláncban vannak azt is lehetővé teszi, hogy akár szövegfájlból is könnyen beolvashatjuk e karaktersorozatot./
A megoldandó táblázatot megjelenítjük az előző, mátrixokról szóló bejegyzésben szereplő mátrix_string() függvény igénybevételével. Ennek kódját itt most nem ismételjük meg.
A feladatot megoldatjuk a sudoku_megoldás() függvénnyel, majd a megoldott, kitöltött táblázatot megjelenítjük.
Ebben a feladatban a ciklus, a listaépítő kifejezés és a rekurzió, illetve rekurzív függvény képezte a lényeget. Ezekről részletesen a Python tudásépítés lépésről lépésre című e-könyv alábbi fejezeteiben van szó: „Műveletek” fejezet – „Különleges műveletek” alfejezet – „Konténerépítés” alcím „Repetázzunk – ciklikus utasítás végrehajtás” fejezet, „Különleges függvénydefiníciók” fejezeten belül az „Amikor a kígyó a farkába harap – függvényrekurzió” alfejezet.