Přístupnostní navigace
E-application
Search Search Close
Bachelor's Thesis
Author of thesis: Bc. Adam Vlček
Acad. year: 2025/2026
Supervisor: prof. RNDr. Alexandr Meduna, CSc.
Reviewer: Ing. Zbyněk Křivka, Ph.D.
This thesis deals with solving sudoku using the theory of formal languages and finite automata. It describes fundamental algorithms used for solving sudoku, mainly backtracking, backtracking with constraint propagation, and simulated annealing. Sudoku is formalized as a two-dimensional word over a finite alphabet and the set of valid solutions is defined as a picture language. The main part of the thesis focuses on the design of an explicit four-way finite automaton intended for sudoku configuration validation. The thesis also introduces an optimized automaton simulation based on the automaton's external memory. The proposed approaches were implemented in a Python application and experimentally compared with respect to validation efficiency and sudoku solving time complexity. The results show that the optimized automaton simulation significantly reduces validation overhead compared to explicit automaton simulation and classical validation functions.
sudoku, backtracking, simulated annealing, finite automata, four-way automaton, formal languages, picture languages, sudoku validation, CSP, Python
Date of defence
15.06.2026
Result of the defence
Defended (thesis was successfully defended)
Grading
E
Process of defence
Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm E.
Topics for thesis defence
Language of thesis
Slovak
Faculty
Fakulta informačních technologií
Department
Department of Information Systems
Study programme
Information Technology (BIT)
Composition of Committee
doc. RNDr. Milan Češka, Ph.D. (předseda) doc. Ing. Jan Kořenek, Ph.D. (místopředseda) Ing. Zdeněk Materna, Ph.D. (člen) Ing. Miloš Musil, Ph.D. (člen) Ing. Martin Hrubý, Ph.D. (člen)
Supervisor’s reportprof. RNDr. Alexandr Meduna, CSc.
Vedoucí zdůvodňuje hodnocení C takto: student získával poznatky ze studijních materiálů průměrným způsobem. Jeho komunikace s vedoucím byla průměrná a nedávala vedoucímu možnost řídit vývoj práce zcela vyčerpávajícím způsobem. Jeho přístup k řešení byl poměrně systematický. Je třeba ale uznat, že téma práce je velmi originální a student se jej svým způsobem snažil řešit, což je třeba ocenit. Tato snaha vede vedoucího k hodnocení C.
Práce byla vypracována dle uvedeného tématu a postupu. Nebyla příliš náročná, ač vyžadovala studium cizojačné literatury a následný rozvoj získaných znalostí. Práce nepřekročila zadání.
Aktivita studenta při získávání a využívání studijních materiálů k řešení bakalářské práce byla průměrná. Setkávali jsme se zhruba jednou za 10 dní a konzultace měly obecný charakter s málo konkétními dotazy z jeho strany.
Student byl během řešení běžně aktivní.
Práce byla dokončena s mírným předstihem. Finální verze práce byla konzultována jen hrubě.
Není.
Grade proposed by supervisor: C
Reviewer’s reportIng. Zbyněk Křivka, Ph.D.
Samotný text je téměř průměrný, implementace není žádný zázrak a není ani moc obecná a rozšiřitelná. Využití dále je diskutabilní. Zadání je splněno minimalisticky, takže navrhuji stupeň D.
Evaluation level: less difficult assignment
Zadání je formulováno jednoduše a dává prostor pro kreativitu řešitele či intenzivnější spolupráci mezi vedoucím a studentem, což se bohužel pravděpodobně nekonalo.
Práce neobsahuje jediný algoritmus, schéma či diagram, které by pomáhaly v pochopení návrhu či implementace.
Důkaz na s. 22 je jednoduchý a hlavně bez formalizace dokazovaného algoritmu je na vodě. V kapitole 9 chybí definování různě náročných úloh, které jsou dále využity pro kategorizaci testovaných úloh.
Kromě dílčích nedostatků je napsán text čtivě a přímočaře, jen škoda, že nejde místy obsahově víc do hloubky i do šířky.
Typograficky je text práce slušný a nenašel jsem mnoho prohřešků (např. neodkazovaný obrázek 8.1). Co jsem schopen posoudit v rámci pravopisu slovenského jazyka, tak je práce napsána bez větších chyb.
Realizační výstup je jednoduchá aplikace s GUI v jazyce Python s implementací v rozsahu asi 1200 řádků kódu, která pracuje v konzistenci s textem práce. Kód je komentovaný a obsahuje několik tříd, ale bez pokročilejšího využití OOP.
Z velmi jednoduchého návrhu jsem získal dojem, že celá implementace pouze ověřuje domněnky ohledně experimentální časové složitosti popsaných přístupů a já další využití aplikace bohužel nevidím.
Evaluation level: assignment almost fulfilled, with major reservations
Dle zadání měl student využít při úvodní analýze pramenu [Bažina, 2024], což se nestalo, nedošlo ani k vymezení současné práce vůči této BP. Dále mám výtku k bodu 4, kdy nemám dojem, že by práce analyzovala dosud zavedené metody, tudíž není jasné, zda uvedené porovnání je vůči zavedeným metodám implementovaným studentem, nebo mezi metodami navrženými a implementovanými studentem.
Evaluation level: meets the minimum requirements only
Ačkoli má samotný text přes 50 normostran, tak jsem měl na řadě míst dojem, že je text bezúčelně natahován. Např. v sekci 9.2 se dokola opakuje potřeba jednoduché optimalizace využívající tří množin. Dále sekce 8.4.3 v podstatě jen opakuje informace z sekce 3.3.
Ve výběru literatury bych kromě literatury vyžadované zadáním očekával i prameny týkající se návrhu GUI, rozšiřitelné implementace a experimentálního ověření složitosti algoritmů apod.
Grade proposed by reviewer: D
Responsibility: Mgr. et Mgr. Hana Odstrčilová