34. Backtracking

Generovanie štvoríc čísel

Napíšme program, ktorý vypíše všetky 4-ciferné čísla zložené len z cifier 0n-1 a pritom žiadna cifra sa neopakuje viackrát. Takéto štvorice budeme generovať štyrmi vnorenými for-cyklami:

n = 4
pocet = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            for l in range(n):
                if i!=j and i!=k and j!=k and i!=l and j!=l and k!=l:
                    print(i, j, k, l)
                    pocet += 1
print('pocet =', pocet)

Program okrem všetkých vyhovujúcich štvoríc vypíše aj ich počet (zrejme pre n=4 ich bude 24, t.j. 4!).

Program môžeme aj trochu vylepšiť: vnútorné cykly nebudú zbytočne skúšať rôzne možnosti napr. vtedy, keď i == j:

n = 4
pocet = 0
for i in range(n):
    for j in range(n):
        if i!=j:
            for k in range(n):
                if i!=k and j!=k:
                    for l in range(n):
                        if i!=l and j!=l and k!=l:
                            print(i, j, k, l)
                            pocet += 1
print('pocet =', pocet)

Jednoduchým vylepšením môžeme generovať nie čísla (z nejakého intervalu), ale slová, ktoré sú zložené len zo zadaných písmen vo vstupnom slove:

slovo = 'ahoj'
pocet = 0
for i in slovo:
    for j in slovo:
        if i!=j:
            for k in slovo:
                if i!=k and j!=k:
                    for l in slovo:
                        if i!=l and j!=l and k!=l:
                            print(i + j + k + l)
                            pocet += 1
print('pocet =', pocet)

Program takto vypíše 24 rôznych slov.

Takýto spôsob riešenia však nie je najvhodnejší. Ak by sme napr. potrebovali nie štvorice, ale všeobecne n-tice číslic, alebo, ak by sme chceli komplikovanejšiu podmienku (cifry sa môžu raz opakovať) a pod., budeme musieť použiť nejaký iný spôsob riešenia.

Rekurzia

Budeme riešiť generovanie n-tíc čísel pomocou rekurzívnej funkcie. Začnime s úlohou, v ktorej generujeme všetky štvorice čísel z intervalu 0n-1, pričom čísla sa môžu aj opakovať. Úlohu budeme riešiť pre ľubovoľné n. n-ticu postupne vytvárame v n-prvkovom zozname pole a keď je kompletná, tak ju vypíšeme:

n = 4
pole = [0] * n

def generuj(i):            # pridaj i-ty prvok do zoznamu pole
    for j in range(n):
        pole[i] = j
        if i == n - 1:
            print(*pole)
        else:
            generuj(i + 1)

generuj(0)

Toto riešenie generuje všetky n-tice čísel a nielen tie, v ktorých sú všetky cifry rôzne (teda 256 štvoríc). Pridáme teraz test na to, či je vygenerovaná n-tica naozaj správne riešenie: t.j. žiadne dva prvky nesmú byť rovnaké. Využijeme na to množinu, ktorú vytvoríme zo všetkých n prvkov zoznamu. Ak je aj táto množina n-prvková, žiaden prvok v zozname sa neopakoval a teda máme vyhovujúce riešenie:

n = 4
pole = [0] * n

def generuj(i):
    for j in range(n):
        pole[i] = j
        if i == n - 1:
            if len(set(pole)) == n:
                print(*pole)
        else:
            generuj(i + 1)

generuj(0)

Program teraz generuje 24 rôznych štvoríc.

Ak by sme ale potrebovali robiť kontrolu priebežne pred každým pridaním ďalšieho čísla, môžeme zapísať:

n = 4
pole = [0] * n

def generuj(i):
    for j in range(n):
        if j not in pole[:i]:    # kontrola, či sme už j nepoužili predtým
            pole[i] = j
            if i == n - 1:
                print(*pole)
            else:
                generuj(i + 1)

generuj(0)

Zapuzdrime

Zvykli sme si zapisovať komplexnejšie programy ako metódy triedy, pričom namiesto globálnych premenných pracujeme s atribútmi triedy. Zapíšme rekurzívne generovanie n-tíc ako metódu triedy Uloha. Začneme s jednoduchou verziou, v ktorej sa ešte nekontroluje, či sa nejaké cifry opakujú:

class Uloha:
    def __init__(self, n):
        self.n = n
        self.pole = [0] * n

    def generuj(self, i):
        for j in range(self.n):
            self.pole[i] = j
            if i == self.n - 1:
                print(*self.pole)
                self.pocet += 1
            else:
                self.generuj(i + 1)

    def ries(self):
        self.pocet = 0
        self.generuj(0)
        print('pocet =', self.pocet)

Uloha(4).ries()

Program vypíše 256 štvoríc.

Doplňme kontrolu, či vygenerovaná štvorica vyhovuje: do metódy vyhovuje zapíšme kontrolu kompletnej štvorice:

class Uloha:
    def __init__(self, n):
        self.n = n
        self.pole = [0] * n

    def vyhovuje(self):
        return len(set(self.pole)) == self.n

    def generuj(self, i):
        for j in range(self.n):
            self.pole[i] = j
            if i == self.n - 1:
                if self.vyhovuje():             # len tie n-tice, ktoré vyhovujú
                    print(*self.pole)
                    self.pocet += 1
            else:
                self.generuj(i + 1)

    def ries(self):
        self.pocet = 0
        self.generuj(0)
        print('pocet =', self.pocet)

Uloha(4).ries()

Takéto riešenie už dáva správny výsledok. Treba si ale uvedomiť, že algoritmus zbytočne generuje dosť veľa štvoríc (256), z ktorých cez výstupnú kontrolu (tesne pred výpisom pripravenej n-tice) prejde len niekoľko z nich (24).

Ukážeme riešenie, v ktorom sa vnárame do rekurzie len vtedy, keď doterajšia vygenerovaná časť riešenia vyhovuje podmienkam. Pripravili sme pomocnú funkciu moze(i, j), ktorá otestuje, či momentálna hodnota j môže byť priradená na i-tu pozíciu výsledného zoznamu pole:

class Uloha:
    def __init__(self, n):
        self.n = n
        self.pole = [0] * n

    def moze(self, i, j):     # či na i-tu pozíciu môžeme dať j
        return j not in self.pole[:i]

    def generuj(self, i):
        for j in range(self.n):
            if self.moze(i, j):
                self.pole[i] = j
                if i == self.n - 1:
                    print(*self.pole)
                    self.pocet += 1
                else:
                    self.generuj(i + 1)

    def ries(self):
        self.pocet = 0
        self.generuj(0)
        print('pocet =', self.pocet)

Uloha(4).ries()

Takže testujeme nie až keď je vytvorená kompletná n-tica, ale vždy pred pridaním ďalšej hodnoty.

Pri riešení niektorých úloh môžeme na kontrolu pridávaného prvku do riešenia využiť ďalšie pomocné štruktúry. Nám by sa tu hodila napr. množina už použitých čísel, prípadne slovník (asociatívne pole dict), v ktorom budeme evidovať počet výskytov každého čísla, napr.

class Uloha:
    def __init__(self, n):
        self.n = n
        self.pole = [0] * n

    def moze(self, j):
        return self.vyskyty[j] == 0

    def generuj(self, i):
        for j in range(self.n):
            if self.moze(j):
                self.pole[i] = j
                self.vyskyty[j] += 1
                if i == self.n - 1:
                    print(*self.pole)
                    self.pocet += 1
                else:
                    self.generuj(i + 1)
                self.vyskyty[j] -= 1

    def ries(self):
        self.pocet = 0
        self.vyskyty = {i:0 for i in range(self.n)}      # zatial su vsetky vyskyty 0
        self.generuj(0)
        print('pocet =', self.pocet)

Uloha(4).ries()

Vidíme tu nový veľmi dôležitý detail:

  • vždy, keď zaevidujeme nový prvok do pripravovaného zoznamu (self.pole[i] = j), zaznačíme ďalší výskyt tejto hodnoty aj do zoznamu vyskyty

  • lenže, takto zaznačený výskyt treba niekedy aj zrušiť, lebo by sme príslušnú hodnotu už nikdy nedostali na žiadnej inej pozícii:

    • samotné zrušenie výskytu (self.vyskyty[j] -= 1) robíme na konci tela cyklu, lebo vtedy sa bude skúšať na túto pozíciu priradiť iná hodnota

Počítadlo výskytov by sme mohli využiť aj v úlohe, kde treba generovať n-tice, ale tak, že každá cifra sa môže raz opakovať. Zmeníme podmienku vo funkcii moze:

def moze(self, j):
    return self.vyskyty[j] <= 1

Pozrite si ešte nasledovný variant rekurzívnej funkcie generuj:

def generuj(self, i):
    if i == self.n:
        print(*self.pole)
        self.pocet += 1
    else:
        for j in range(self.n):
            if self.moze(j):
                self.pole[i] = j
                self.vyskyty[j] += 1
                self.generuj(i + 1)
                self.vyskyty[j] -= 1

Takto zapísaná metóda funguje presne rovnako ako predchádzajúca verzia, len sa testovanie, či je kompletné riešenie, presunulo na začiatok (aj s malou zmenou podmienky). V praxi si väčšinou vyberáme ten zápis, ktorý sa nám v konkrétnej situácii viac hodí (nižšie uvidíme aj ďalšie varianty).

Backtracking

Takéto generovanie všetkých možných n-tíc, ktoré spĺňajú nejakú podmienku, je základom algoritmu, ktorému hovoríme prehľadávanie s návratom, resp. backtracking. Tento algoritmus teda:

  • v každom kroku vyskúša všetky možnosti (napr. pomocou for-cyklu)

  • pre každú možnosť preverí, či spĺňa podmienky (napr. metódou moze(...))

  • ak áno, zaeviduje si túto hodnotu (hovoríme tomu, že sa zaznačí ťah) väčšinou v nejakých interných štruktúrach (zoznam, množina, slovník, …)

  • skontroluje, či riešenie nie je už kompletné a vtedy ho spracuje (napr. ho vypíše, alebo niekam zaznačí)

  • ak riešenie ešte nie je kompletné, treba generovať ďalší prvok, čo zabezpečí rekurzívne volanie

  • na konci cyklu, v ktorom sa postupne skúšajú všetky možnosti, treba ešte vrátiť stav pred zaevidovaním hodnoty (hovoríme tomu, že sa odznačí ťah)

Schematicky to môžeme zapísať takto:

def backtracking(param):
    for i in vsetky_moznosti:
        if moze(i):
            zaznac_tah(i)
            if hotovo:
                vypis_riesenie()
            else:
                backtracking(param1)
            odznac_tah(i)

alebo druhá schéma:

def backtracking(param):
    if hotovo:
        vypis_riesenie()
    else:
        for i in vsetky_moznosti:
            if moze(i):
                zaznac_tah(i)
                backtracking(param1)
                odznac_tah(i)

Zapamätajte si, že je veľmi dôležité vrátiť ešte pred koncom cyklu všetko, čo sme zaevidovali na začiatku cyklu. Uvedomte si, že bez tohto vrátenia pôvodného stavu sa tento algoritmus stáva obyčajným prehľadávaním do hĺbky, ktorý sa len rekurzívne vnára hlbšie a hlbšie …

Pomocou backtrackingu môžeme riešiť úlohy typu:

  • matematické hlavolamy (8 dám na šachovnici, domček jedným ťahom, kôň na šachovnici, sudoku, …)

  • rôzne problémy na grafoch (nájsť cestu s najmenším ohodnotením z A do B, vyhodiť max. počet hrán, aby platila nejaká podmienka)

Vo všeobecnosti je backtracking veľmi neefektívny algoritmus (patrí medzi algoritmy tzv. hrubá sila, brute force), pomocou ktorého sa dá vyriešiť veľké množstvo úloh (postupne vyskúšam všetky možnosti). V praxi sa mnoho problémov dá vyriešiť oveľa efektívnejšie. Pre backtracking väčšinou platí, že jeho zložitosť je exponenciálna, t.j. čím je úloha väčšieho rozsahu, tým rýchlejšie rastie čas na jeho vyriešenie. Pri algoritmoch triedenia sme videli obrovský rozdiel vo výkone bublinkového a rýchleho (quick-sort) triedenia. Pritom bublinkové triedenie má zložitosť rádovo n**2 a pre väčší zoznam je už neprijateľne pomalé. Čo potom algoritmy, ktorých zložitosť je rádovo 2**n.

Dámy na šachovnici

Budeme riešiť takýto hlavolam: na šachovnicu s 8x8 treba umiestniť 8 dám tak, aby sa navzájom neohrozovali (vodorovne, zvislo ani uhlopriečne). Zrejme v každom riadku a tiež v každom stĺpci musí byť práve jedna dáma. Dámy očíslujeme číslami od 0 do 7 tak, že i-ta dáma sa bude nachádzať v i-tom riadku. Potom každé rozloženie dám na šachovnici môžeme reprezentovať osmicou čísel (v zozname riesenie): i-te číslo potom určuje číslo stĺpca i-tej dámy.

Na riešenie úlohy využime schému backtrackingu:

def hladaj(self, i):          # i-ta dáma v i.riadku -> hľadá pre ňu vhodný stĺpec
    for j in range(self.n):
        if self.moze(i, j):
            # zaznač položenie dámy
            self.riesenie[i] = j
            ...
            if i == self.n - 1:             # ak je už hotovo
                print(*self.riesenie)
                self.pocet += 1
            else:
                self.hladaj(i + 1)
            # odznač položenie dámy
            self.riesenie[i] = None
            ...

Na rýchle otestovanie, či je nejaká pozícia ohrozená ostatnými dámami použijeme 3 pomocné množiny:

  • stlpec - tu si pamätáme, v ktorých stĺpcoch je už nejaká dáma

  • u1 - pamätáme si, v ktorých uhlopriečkach (sprava doľava) je už nejaká dáma

  • u2 - pamätáme si, v ktorých uhlopriečkach (zľava doprava) je už nejaká dáma

Využijeme vlastnosť políčok na šachovnici, vďaka ktorej vieme zistiť, či sa dve políčka nachádzajú na tej istej uhlopriečke:

  • pre uhlopriečky sprava (hore) doľava (dole) platí, že súčet čísla riadku a čísla stĺpca je rovnaký (napr. (3,1),(2,2),(0,4),… ležia na jednej uhlopriečke)

  • pre uhlopriečky zľava (hore) doprava (dole) platí, že rozdiel čísla riadku a čísla stĺpca je rovnaký (napr. (3,1),(4,2),(6,4),… ležia na jednej uhlopriečke)

Všetky tieto tri pomocné množiny musia byť na začiatku prázdne:

self.stlpec = set()
self.u1 = set()
self.u2 = set()

Zaznačiť ťah potom znamená:

  • zapamätať si ho v zozname riesenie

  • zaznačiť si obsadený príslušný stĺpec v množine stlpec

  • zaznačiť si obsadenú príslušnú uhlopriečku v množine u1

  • zaznačiť si obsadenú príslušnú 2. uhlopriečku v množine u2

# zaeviduj i-tu dámu v i riadku a j stĺpci
self.riesenie[i] = j
self.stlpec.add(j)
self.u1.add(i+j)
self.u2.add(i-j)

Kontrola jednej konkrétnej dámy (metóda moze()) potom len skontroluje tieto tri množiny:

def moze(self, i, j):         # či môže položiť dámu na pozíciu (i, j)
    return j not in self.stlpec and i + j not in self.u1 and i - j not in self.u2

Celý program:

class Damy:
    def __init__(self, n):
        self.n = n
        self.riesenie = [None] * n

    def moze(self, i, j):         # či môže položiť dámu na pozíciu (i, j)
        return (j not in self.stlpec and
                i + j not in self.u1 and
                i - j not in self.u2)

    def hladaj(self, i):          # i-ta dáma v i.riadku -> hľadá pre ňu vhodný stĺpec
        for j in range(self.n):
            if self.moze(i, j):
                # zaznač položenie dámy
                self.riesenie[i] = j
                self.stlpec.add(j)
                self.u1.add(i + j)
                self.u2.add(i - j)
                if i == self.n - 1:
                    print(*self.riesenie)
                    self.pocet += 1
                else:
                    self.hladaj(i + 1)
                # odznač položenie dámy
                self.riesenie[i] = None
                self.stlpec.remove(j)
                self.u1.remove(i + j)
                self.u2.remove(i - j)

    def ries(self):
        self.stlpec = set()
        self.u1 = set()
        self.u2 = set()
        self.pocet = 0
        self.hladaj(0)
        print('pocet rieseni:', self.pocet)

Damy(8).ries()

Rekurzívnu metódu hladaj() by sme mohli prepísať aj podľa druhej schémy backtrackingu:

def hladaj(self, i):          # i-ta dáma v i.riadku -> hľadá pre ňu stĺpec
    if i == self.n:
        print(*self.riesenie)
        self.pocet += 1
    else:
        for j in range(self.n):
            if self.moze(i, j):
                # zaznač položenie dámy
                self.riesenie[i] = j
                self.stlpec.add(j)
                self.u1.add(i + j)
                self.u2.add(i - j)
                self.hladaj(i + 1)
                # odznač položenie dámy
                self.riesenie[i] = None
                self.stlpec.remove(j)
                self.u1.remove(i + j)
                self.u2.remove(i - j)

Výsledný program aj teraz generuje rovnaký výsledok.

Niekedy potrebujeme organizovať backtrackingovú funkciu tak, že priamo v parametroch funkcie dostane konkrétnu hodnotu ťahu - vtedy si ho najprv zaznačí, potom vygeneruje ďalší ťah (rekurzívne sa zavolá) a na koniec odznačí ťah.

Úlohu s dámami môžeme zapísať aj takto:

class Damy:
    def __init__(self, n):
        self.n = n
        self.riesenie = [None] * n

    def moze(self, i, j):         # či môže položiť dámu na pozíciu (i, j)
        return (j not in self.stlpec and
                i + j not in self.u1 and
                i - j not in self.u2)

    def dalsia(self, i, j):        # polož ďalšiu dámu na (i, j)
        # zaznač položenie dámy
        self.riesenie[i] = j
        self.stlpec.add(j)
        self.u1.add(i + j)
        self.u2.add(i - j)

        if i == self.n-1:
            print(*self.riesenie)
            self.pocet += 1
        else:
            for k in range(self.n):
                if self.moze(i + 1, k):
                    self.dalsia(i + 1, k)

        # odznač položenie dámy
        self.riesenie[i] = None
        self.stlpec.remove(j)
        self.u1.remove(i + j)
        self.u2.remove(i - j)

    def ries(self):
        self.stlpec = set()
        self.u1 = set()
        self.u2 = set()
        self.pocet = 0
        for j in range(self.n):
            self.dalsia(0, j)
        print('pocet rieseni:', self.pocet)

Damy(8).ries()

Backtracking sme namiesto metódy hladaj() zapísali metódou dalsia().

Ďalšia verzia tohto programu ukazuje, ako môžeme vykresliť nájdené riešenie (metóda vypis()). Tiež sme na začiatok backtrackingu pridali jeden test, vďaka ktorému program korektne skončí po nájdení a vypísaní jedného riešenia (ak nám jedno stačí):

class Damy:
    def __init__(self, n):
        self.n = n
        self.riesenie = [None] * n

    def moze(self, i, j):         # či môže položiť dámu na pozíciu (i,j)
        return (j not in self.stlpec and
                i + j not in self.u1 and
                i - j not in self.u2)

    def vypis(self):
        for k in range(self.n):
            r = ['.'] * self.n
            r[self.riesenie[k]] = 'o'
            print(' '.join(r))
        print('=' * 2 * self.n)

    def hladaj(self, i):
        if self.pocet:               # už máme 1 riešenie, nemusíme ďalej pokračovať
            return
        for j in range(self.n):
            if self.moze(i, j):
                # zaznač položenie dámy
                self.riesenie[i] = j
                self.stlpec.add(j)
                self.u1.add(i+j)
                self.u2.add(i-j)
                if i == self.n-1:
                    self.vypis()
                    self.pocet += 1
                else:
                    self.hladaj(i+1)
                # odznač položenie dámy
                self.riesenie[i] = None
                self.stlpec.remove(j)
                self.u1.remove(i+j)
                self.u2.remove(i-j)

    def ries(self):
        self.stlpec = set()
        self.u1 = set()
        self.u2 = set()
        self.pocet = 0
        self.hladaj(0)
        # print('pocet rieseni:', self.pocet)
        if self.pocet == 0:
            print('ziadne riesenie')

Damy(8).ries()

Domček jedným ťahom

Budeme riešiť takúto úlohu: potrebujeme zistiť, koľkými rôznymi spôsobmi sa dá nakresliť takýto domček jedným ťahom. Pri kreslení môžeme po každej čiare prejsť len raz.

_images/34_1.png

Obrázok domčeka je vlastne neorientovaný graf s 5 vrcholmi. Každé nájdené riešenie vypíšeme v tvare postupnosti vrcholov, cez ktoré sa prechádza pri kreslení domčeka. Keďže hrán je v grafe 8, tak táto postupnosť bude obsahovať presne 9 vrcholov: jeden štartový a 8 nasledovných vrcholov.

Graf budeme reprezentovať čo najjednoduchšie, napr. pomocou zoznamu množín susedností. Pre každý z vrcholov si treba pamätať množinu jeho susedov:

graf = [{1,2,3},      # susedia vrcholu 0
        {0,2,3},      # susedia vrcholu 1
        {0,1,3,4},    # susedia vrcholu 2
        {0,1,2,4},    # susedia vrcholu 3
        {2,3},        # susedia vrcholu 4
        ]

Kompletný program postupne vytvára zoznam riesenie s postupnosťou prechádzaných vrcholov grafu:

class Domcek:
    def __init__(self):
        self.g = [{1,2,3}, {0,2,3}, {0,1,3,4}, {0,1,2,4}, {2,3}]

    def hladaj(self):
        v1 = self.riesenie[-1]
        for v2 in sorted(self.g[v1]):
            # zaznac tah
            self.riesenie.append(v2)
            self.g[v1].remove(v2)
            self.g[v2].remove(v1)
            if len(self.riesenie) == 9:     # zišlo by sa prepočítať
                print(*self.riesenie)
                self.pocet += 1
            else:
                self.hladaj()
            # odznac tah
            self.riesenie.pop()
            self.g[v1].add(v2)
            self.g[v2].add(v1)

    def ries(self):
        self.pocet = 0
        for i in range(len(self.g)):    # postupne vyskúša pre všetky vrcholy
            self.riesenie = [i]
            self.hladaj()
        print('pocet rieseni:', self.pocet)

Domcek().ries()
  • prvý vrchol riešenia (štartový) sa do zoznamu priraďuje ešte pred zavolaním backtrackingu v štartovej metóde ries: keďže môžeme začínať z ľubovoľného vrcholu, v tejto metóde štartujeme backtracking v cykle postupne so všetkými možnými začiatočnými vrcholmi

  • v backtrackingovej metóde hladaj:

    • v1 obsahuje zatiaľ posledný vrchol riešenia, na ktorý bude teraz nadväzovať nasledovný vrchol v2

    • zaznačenie ťahu uskutočníme tak, že práve prejdenú hranu dočasne z grafu odstránime (graf je neorientovaný preto treba odstraňovať oba smery tejto hrany)

    • riešenie je kompletné vtedy, keď obsahuje presne 9 vrcholov

    • odznačenie ťahu (teda návrat do pôvodného stavu pred zaznačením) urobíme vrátením dočasne odstránenej hrany

Sudoku

Pomocou prehľadávania do hĺbky vyriešime veľmi populárny hlavolam Sudoku. Hracia plocha sa skladá z 9x9 políčok. Na začiatku sú do niektorých políčok zapísané čísla z intervalu <1,9>. Úlohou je zapísať aj do zvyšných políčok čísla 1 až 9 tak, aby v každom riadku a tiež v každom stĺpci bolo každé z čísel práve raz. Okrem toho je celá plocha rozdelená na 9 menších štvorcov veľkosti 3x3 - aj v každom z týchto štvorcov musí byť každé z čísel práve raz.

Napr. súbor s konkrétnym zadaním 'sudoku.txt' môže vyzerať napr. takto:

0 6 0 9 0 0 0 7 0
0 4 0 8 0 0 0 0 0
0 0 0 0 5 0 3 0 0
0 0 0 0 0 0 0 0 0
0 9 0 0 4 0 0 6 0
8 0 5 0 6 0 0 0 0
7 0 8 3 0 0 0 0 4
3 0 0 0 2 1 0 0 8
0 0 0 0 0 0 0 0 2
  • hodnota 0 označuje, že príslušné políčko je zatiaľ prázdne

Samotná backtrackingová rekurzívna procedúra najprv nájde prvé zatiaľ voľné políčko (je tam hodnota 0). Potom sa sem pokúsi zapísať všetky možnosti čísel 1 až 9. Zakaždým otestuje, či zapisované číslo sa v príslušnom riadku, stĺpci a tiež v malom 3x3 štvorci ešte nenachádza:

def backtracking(self):
    i, j = najdi_volne()      # nájdi voľné políčko
    if nenasiel:              # už nie je žiadne ďalšie voľné políčko
        vypis_riesenie()
    else:
        for cislo in range(1, 10):         # pre všetky možnosti čísel od 1 do 9
            if moze(i, j, cislo):
                zaznac_tah()
                backtracking()
                odznac_tah()

Aby sa nám čo najjednoduchšie testovalo, či sa nejaké číslo ešte nenachádza v príslušnom riadku, stĺpci a 3x3 štvorci, pre každý riadok, stĺpec aj štvorec 3x3 zavedieme množinovú premennú, t.j. 9-prvkové množinové zoznamy pre riadky a stĺpce a dvojrozmerný 3x3 zoznam (matica) množín pre menšie štvorce:

self.vstlpci = [set(),set(),set(),set(),set(),set(),set(),set(),set()]
self.vriadku = [set(),set(),set(),set(),set(),set(),set(),set(),set()]
self.v3x3    = [[set(),set(),set()], [set(),set(),set()], [set(),set(),set()]]

Ak budeme teraz potrebovať zistiť, či sa v j-tom stĺpci nachádza dané cislo zapíšeme:

if cislo in self.vstlpci[j]: ...

podobne pre i-ty riadok:

if cislo in self.vriadku[j]: ...

alebo v príslušnom malom štvorci 3x3 (chceme zistiť štvorec, ktorý obsahuje políčko (i,j) teda i aj j delíme 3):

if cislo in self.v3x3[i // 3][j // 3]: ...

Podobným spôsobom budeme do týchto množín vkladať nové čísla (pri zaznačovaní ťahu), resp. ich z množín odoberať (pri odznačovaní).

Všimnite si, že tieto množiny sa musia zaplniť počiatočnými hodnotami už pri čítaní vstupného súboru. Kompletný program:

class Sudoku:
    def __init__(self, subor):
        with open(subor) as subor:
            self.tab = [[int(i) for i in r.split()] for r in subor]
        self.vstlpci = [set() for i in range(9)]
        self.vriadku = [set() for i in range(9)]
        self.v3x3    = [[set(), set(), set()] for i in range(3)]
        for i in range(9):
            for j in range(9):
                cislo = self.tab[i][j]
                if cislo:
                    self.vstlpci[j].add(cislo)
                    self.vriadku[i].add(cislo)
                    self.v3x3[i // 3][j // 3].add(cislo)

    def vypis(self):
        if self.pocet == 0:                 # vypíše len prvé riešenie
            for riadok in self.tab:
                print(*riadok)
            print('=' * 17)

    def moze(self, i, j, cislo):
        return (cislo not in self.vstlpci[j] and
                cislo not in self.vriadku[i] and
                cislo not in self.v3x3[i // 3][j // 3])

    def backtracking(self):
        i = j = 0
        while i < 9 and self.tab[i][j]:
            j += 1
            if j == 9:
                i += 1
                j = 0
        if i == 9:                   # už nie je žiadne ďalšie voľné políčko
            self.vypis()
            self.pocet += 1
        else:
            for cislo in range(1, 10):
                if self.moze(i, j, cislo):
                    self.tab[i][j] = cislo
                    self.vstlpci[j].add(cislo)
                    self.vriadku[i].add(cislo)
                    self.v3x3[i // 3][j // 3].add(cislo)
                    self.backtracking()
                    self.tab[i][j] = 0
                    self.vstlpci[j].remove(cislo)
                    self.vriadku[i].remove(cislo)
                    self.v3x3[i // 3][j // 3].remove(cislo)

    def ries(self):
        self.pocet = 0
        self.backtracking()
        print('pocet rieseni:', self.pocet)

Sudoku('sudoku.txt').ries()


Cvičenia

L.I.S.T.

  1. Napíš funkciu vypis_rastuce(n), ktorá vygeneruje a vypíše všetky n-tice čísel z <0, n-1>. Pre tieto vygenerované postupnosti musí platiť, že i-ty prvok nie je väčší ako (i+1)-ty.

    • funkcia by nemala používať žiadne globálne premenné (napr. pole)

    • napr.

      >>> vypis_rastuce(2)
      0 0
      0 1
      1 1
      >>> vypis_rastuce(3)
      0 0 0
      0 0 1
      0 0 2
      0 1 1
      0 1 2
      0 2 2
      1 1 1
      1 1 2
      1 2 2
      2 2 2
      
    • pomôcka: môžeš využiť generovanie n-tíc z prednášky, pričom samotnú rekurzívnu funkciu vnoríš do funkcie vypis_rastuce():

      def vypis_rastuce(n):
          def generuj(i):
              ...
                  generuj(i + 1)
      
          pole = [0] * n
          generuj(0)
      
      vypis_rastuce(2)
      vypis_rastuce(3)
      

  1. Napíš funkciu vsetky(mnozina), ktorá pre danú množinu písmen (kde počet písmen v množine je n) vygeneruje a vypíše všetky n-znakové slová, ktoré obsahujú len písmená z danej množiny

    • napr. (výpis v ľubovoľnom poradí):

      >>> vsetky({'x', 'y'})
      xx
      xy
      yx
      yy
      
    • pomôcka: opäť využiješ vnorenú rekurzívnu funkciu, napr.:

      def vsetky(mnozina):
          def generuj():
              ...
                  generuj()
      
          slovo = []
          generuj()
      
      vsetky({'x', 'y'})
      vsetky(set('ahoj'))
      

  1. Napíš funkciu vsetky_len_raz(mnozina), ktorá pre danú množinu písmen (kde počet písmen v množine je n) vygeneruje a vypíše všetky n-znakové slová, ktoré obsahujú všetky písmená z množiny (každé práve raz)

    • napr.

      >>> vsetky_len_raz({'a', 'k', 'm'})
      akm
      amk
      kam
      kma
      mak
      mka
      
    • pomôcka: do riešenia z úlohy (2) pridaj test, ktorým zistíš, či sa pridávaný znak už nenachádza vo vytváranom slove:

      def vsetky_len_raz(mnozina):
          ...
      

  1. Úlohy (2) a (3) rieš tak, aby funkcie nič nevypisovali (pomocou print()), ale namiesto toho vrátili zoznam (alebo množinu) všetkých vygenerovaných slov

    • napr.

      >>> vsetky_zoznam({'x', 'y'})
      ['xx', 'xy', 'yx', 'yy']
      >>> vsetky_len_raz_zoznam(set('akm'))
      ['akm', 'amk', 'kam', 'kma', 'mak', 'mka']
      

  1. Spojazdni riešenie úlohy Dámy na šachovnici z prednášky a uprav ho tak, aby sa vypísali len prvé tri nájdené riešenia aj s celkovým počtom všetkých riešení v tvare:

    • napr.

      >>> Damy(8).ries()
      o . . . . . . .
      . . . . o . . .
      . . . . . . . o
      . . . . . o . .
      . . o . . . . .
      . . . . . . o .
      . o . . . . . .
      . . . o . . . .
      ================
      ...
      pocet rieseni: 92
      

  1. Uprav program pre riešenie úlohy Dámy na šachovnici, ktorý n-dám rozmiestňoval na šachovnici n x n tak, aby našiel všetky riešenia pre n-dám na šachovnici n x m, kde n <= m

    • napr.

      >>> Damy(2, 3).ries()            # šachovnica veľkosti 2x3
      o . .
      . . o
      =====
      . . o
      o . .
      =====
      pocet rieseni: 2
      
    • class Damy:
          def __init__(self, n, m):
              self.n, self.m = n, m
              ...
      
      Damy(2, 3).ries()
      Damy(3, 4).ries()
      

  1. Rieš takýto problém:

    • n žiakov sa prihlásilo na k rôznych krúžkov (každý žiak si zvolil svoju množinu krúžkov)

    • keďže kapacita každého krúžku je obmedzená (hodnotou limit), vedenie školy rozhodlo, že každý žiak bude navštevovať len jeden z krúžkov, do ktorých sa prihlásil

    • priraď každého žiaka do jedného z krúžkov tak, aby sa nepresiahol zadaný limit a pritom by každý zo žiakov chodil do jedného zo svojich zvolených krúžkov

    • napr. takto vyzerá textový súbor s menami žiakov a ich vybraných krúžkov:

      ana kreslenie sach foto
      boris futbal kreslenie
      cyril futbal foto
      dasa foto
      eva sach kreslenie
      fero futbal sach
      gusto futbal kreslenie
      hana kreslenie foto sach
      ivan kreslenie futbal
      jana foto sach
      karol kreslenie foto
      lucia sach futbal
      
    • vypíš ku každému krúžku zoznam žiakov, napr. pre limit = 3 môže byť takýto výsledok:

      kreslenie: eva ivan karol
      sach: jana lucia fero
      futbal: cyril boris gusto
      foto: hana dasa ana
      
    • pomôcka:

      • prečítaj súbor a informácie uchovaj v slovníkoch (asociatívnych poliach), v ktorých každý žiak má priradenú svoju množinu krúžkov, napr.

        ziak['ana'] = {'kreslenie', 'sach', 'foto'}
        ziak['boris'] = {'futbal', 'kreslenie'}
        ...
        
      • ďalej priprav slovníky, kde pre každý krúžok najpr priradíš prázdnu množinu (sem sa budú postupne pridávať žiaci, resp. sa budú odoberať), napr.

        kruzok['kreslenie'] = set()
        kruzok['sach'] = set()
        ...
        
      • rekurzívny backtracking spracuje jedno meno žiaka (postupne ho vkladá do príslušných množín krúžkov) a zakaždým sa rekurzívne zavolá s nasledovným menom žiaka

      • keď už sa spracovali všetci žiaci, vypíšu sa množiny krúžkov a prehľadávanie môže skončiť (stačí nám jedno riešenie, lebo ich môže byť veľmi veľa)


  1. Spojazdni riešenie úlohy Domček jedným ťahom z prednášky a uprav ho tak, aby fungovalo pre takto upravený domček:

    _images/34_2.png

  1. Ručne zisti, čo vygeneruje tento backtracking

    • všimni si, že tab je dvojrozmerným zoznamom (maticou) znakov:

      def backtracking(r, s):
          if 0 <= r < len(tab) and 0 <= s < len(tab[r]):
              if tab[r][s] == 'x':
                  print('\n'.join(' '.join(r) for r in tab), '\n')
              elif tab[r][s] == '.':
                  tab[r][s] = '-'
                  backtracking(r, s + 1)
                  tab[r][s] = '|'
                  backtracking(r + 1, s)
                  tab[r][s] = '\\'               # '\\' označuje jeden znak \
                  backtracking(r + 1, s + 1)
                  tab[r][s] = '.'
      
      tab = [list(r) for r in ('...', '..x')]
      backtracking(0, 0)
      

  1. Zmenou zoznamu v predchádzajúcom príklade sa mení aj výpis vygenerovaných riešení

    • zisti, koľko rôznych riešení sa vygeneruje pre takto definovaný dvojrozmerný zoznam tab:

      tab = [list(r) for r in '... .m. ..x'.split()]
      

      alebo:

      tab = list(map(list, '...m ..m. .m.. m..x'.split()))
      

  1. Uprav funkciu backtracking() z úlohy (9) tak, aby nevypisovala všetky riešenia, len vrátila počet všetkých riešení

    • funkciu zapuzdri do nejakej triedy tak, aby fungovalo, napr.

      >>> Uloha('... ..x').pocet()
      5
      >>> Uloha('... .m. ..x').pocet()
      4
      >>> Uloha('...m ..m. .m.. m..x'.).pocet()
      11
      


11. Domáce zadanie

L.I.S.T.

Zadanie skúšky 3.6.2015: Písmenkový graf

Máme daný neorientovaný graf, v ktorom sa na niektorých hranách môže nachádzať nejaké písmeno z množiny {'a', 'b', 'c'}. Ostatné hrany sú tzv. neoznačené. Vašou úlohou bude zostaviť čo najdlhšiu cestu, ktorá vychádza z nejakého zadaného štartového vrcholu a pre ktorú platí:

  • prvá hrana v ceste má označenie 'a' alebo je bez označenia

  • druhá hrana v ceste má označenie 'b' alebo je bez označenia

  • atď. na hranách cesty sa stále striedajú písmená 'a', 'b', 'c', 'a', 'b', 'c', …, resp. niektoré hrany v ceste môžu byť neoznačené (fungujú niečo ako žolík)

  • cesta môže prechádzať aj viackrát cez tie isté vrcholy ale po hranách môže prejsť len raz

Vašou úlohou je prečítať textový súbor s popisom grafu a po zadaní štartového vrcholu vygenerovať všetky maximálne dlhé cesty, ktoré spĺňajú pravidlo striedania písmen.

Riešenie zapíšte do triedy Graf s týmito metódami:

class Graf:
    def __init__(self, meno_suboru):
        ...

    def hrana(self, v1, v2):
        return None

    def vrcholy(self):
        return set()

    def ries(self, v1):
        return []

Kde metódy:

  • __init__(meno_suboru): prečíta súbor a vytvorí z neho nejakú reprezentáciu neorientovaného ohodnoteného grafu

  • hrana(v1, v2): vráti hodnotu hrany: buď je to jedno z písmen {'a', 'b', 'c'}, alebo prázdny reťazec '' pre neoznačenú hranu, alebo None, ak neexistuje hrana medzi týmito dvoma vrcholmi

  • vrcholy(): vráti množinu mien všetkých vrcholov

  • ries(v1): pomocou backtrackingu nájde všetky najdlhšie cesty z vrcholu v1 – metóda vráti buď prázdny zoznam (nenašiel žiadne riešenie, ktoré by obsahovalo aspoň jednu hranu), alebo zoznam (typ list), ktoré obsahuje všetky najdlhšie cesty; cesta je postupnosť (list) mien vrcholov

Môžete si dodefinovať aj ďalšie pomocné metódy.

Textový súbor obsahuje popis grafu v tvare:

  • každý riadok obsahuje popis jednej hrany grafu buď ako dvojicu alebo ako trojicu

  • dvojica v tvare meno1:meno2 označuje hranu bez písmena (žolík)

  • trojica v tvare meno1:písmeno:meno2 označuje hranu so zadaným písmenom

  • mená vrcholov sú nejaké znakové reťazce zložené len z písmen

  • uvedomte si, že v neorientovanom grafe by mala byť každá hrana orientovaná oboma smermi

  • môžete predpokladať, že súbor je zadaný korektne

Napr. súbor

mo:b:ix
ub:c:mo
ix:ub
er:c:ix
qa:a:ix
er:qa
ub:er
qa:c:ub

označuje graf s piatimi vrcholmi a 8 hranami, pričom niektoré majú označenie a niektoré nie.

Program môžete testovať napríklad takto:

if __name__ == '__main__':
    g = Graf('subor1.txt')
    print('vrcholy =', g.vrcholy())
    for v1, v2 in ('mo', 'ub'), ('er', 'ub'), ('er', 'mo'):
        print(f'hrana({v1!r},{v2!r}) = {g.hrana(v1,v2)!r}')
    riesenie = g.ries('qa')
    print('pocet rieseni =', len(riesenie))
    print(*riesenie, sep='\n')

a pre vyššie uvedený textový súbor by mal vypísať:

vrcholy = {'er', 'ix', 'ub', 'qa', 'mo'}
hrana('mo','ub') = 'c'
hrana('er','ub') = ''
hrana('er','mo') = None
pocet rieseni = 2
['qa', 'er', 'ub', 'qa', 'ix', 'mo', 'ub', 'ix']
['qa', 'ix', 'mo', 'ub', 'er', 'qa', 'ub', 'ix']

Za vyriešenie skúškovej úlohy môžete získať 10 bodov, pričom:

  • 20% je za vytvorenie grafu zo súboru, t.j. správne fungovanie metód vrcholy() a hrana()

  • 20% je za nájdenie nejakého aspoň jedného správneho riešenia, nemusí byť maximálnej dĺžky, ale malo by byť dostatočne dlhé

  • 30% za nájdenie aspoň jedného maximálneho riešenia

  • 30% za nájdenie všetkých maximálnych riešení

Obmedzenia

  • vaše riešenie odovzdajte v súbore riesenie11.py, pričom sa v ňom bude nachádzať len jedna definícia triedy Graf.

  • prvé tri riadky tohto súboru budú obsahovať:

    # 11. zadanie: pismenkovy graf
    # autor: Janko Hrasko
    # datum: 9.5.2019
    
  • zrejme ako autora uvediete svoje meno

  • váš program by nemal počas testovania testovačom nič vypisovať (žiadne vaše testovacie print())

  • testovač bude spúšťať vašu definíciu triedy s rôznymi textovými súbormi, ktoré si môžete stiahnuť z L.I.S.T.u