{"id":{"repo_id":"brno-tech","oai_identifier":"oai:dspace.vut.cz:11012/258129"},"canonical_url":"https://search.dev.ndltd.org/etd/brno-tech/oai:dspace.vut.cz:11012/258129","repository":{"repo_id":"brno-tech","name":"Brno University of Technology","base_url":"https://dspace.vut.cz/oai/request"},"display":{"title":"Řešení sudoku pomocí automatů","abstract":"Táto práca sa zaoberá riešením sudoku pomocou teórie formálnych jazykov a konečných automatov. Opisuje základné algoritmy používané pri riešení sudoku, najmä spätné vyhľadávanie, spätné vyhľadávanie so šírením obmedzení a simulované žíhanie. Sudoku je formalizované ako dvojrozmerné slovo nad konečnou abecedou a množina správnych riešení je definovaná ako jazyk obrazcov. Hlavnou časťou práce je návrh explicitného štvorcestného automatu určeného na validáciu konfigurácií sudoku. Súčasťou práce je aj návrh optimalizovanej simulácie automatu založenej na externej pamäti automatu. Navrhnuté prístupy boli implementované v aplikácii vytvorenej v jazyku Python a experimentálne porovnané z hľadiska efektivity validácie a časovej náročnosti riešenia sudoku. Výsledky ukazujú, že optimalizovaná simulácia automatu výrazne redukuje režijné náklady validácie oproti explicitnej simulácii automatu a klasickým validačným funkciám.","abstract_html":"Táto práca sa zaoberá riešením sudoku pomocou teórie formálnych jazykov a konečných automatov. Opisuje základné algoritmy používané pri riešení sudoku, najmä spätné vyhľadávanie, spätné vyhľadávanie so šírením obmedzení a simulované žíhanie. Sudoku je formalizované ako dvojrozmerné slovo nad konečnou abecedou a množina správnych riešení je definovaná ako jazyk obrazcov. Hlavnou časťou práce je návrh explicitného štvorcestného automatu určeného na validáciu konfigurácií sudoku. Súčasťou práce je aj návrh optimalizovanej simulácie automatu založenej na externej pamäti automatu. Navrhnuté prístupy boli implementované v aplikácii vytvorenej v jazyku Python a experimentálne porovnané z hľadiska efektivity validácie a časovej náročnosti riešenia sudoku. Výsledky ukazujú, že optimalizovaná simulácia automatu výrazne redukuje režijné náklady validácie oproti explicitnej simulácii automatu a klasickým validačným funkciám.","abstract_has_math":false,"creators":["Vlček, Adam"],"institution":"Vysoké učení technické v Brně. Fakulta informačních technologií","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Meduna, Alexandr"],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-07-24T01:22:29Z","subjects":["sudoku","spätné vyhľadávanie","simulované žíhanie","konečné automaty","štvorcestný automat","formálne jazyky","jazyky obrazcov","validácia sudoku","CSP","Python","backtracking","simulated annealing","finite automata","four-way automaton","formal languages","picture languages","sudoku validation"],"languages":["sk"],"rights":["Standardní licenční smlouva - přístup k plnému textu bez omezení"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["168964"],"render_values":[{"text":"168964","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/11012/258129","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Meduna, Alexandr"]},{"key":"dc:creator","label":"Author","values":["Vlček, Adam"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:publisher","label":"Institution","values":["Vysoké učení technické v Brně. Fakulta informačních technologií"]},{"key":"dc:type","label":"Dc Type","values":["Text"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Bc."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["sudoku","spätné vyhľadávanie","simulované žíhanie","konečné automaty","štvorcestný automat","formálne jazyky","jazyky obrazcov","validácia sudoku","CSP","Python","backtracking","simulated annealing","finite automata","four-way automaton","formal languages","picture languages","sudoku validation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["sk"]},{"key":"dc:rights","label":"Dc Rights","values":["Standardní licenční smlouva - přístup k plnému textu bez omezení"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["168964"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11012/258129"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Táto práca sa zaoberá riešením sudoku pomocou teórie formálnych jazykov a konečných automatov. Opisuje základné algoritmy používané pri riešení sudoku, najmä spätné vyhľadávanie, spätné vyhľadávanie so šírením obmedzení a simulované žíhanie. Sudoku je formalizované ako dvojrozmerné slovo nad konečnou abecedou a množina správnych riešení je definovaná ako jazyk obrazcov. Hlavnou časťou práce je návrh explicitného štvorcestného automatu určeného na validáciu konfigurácií sudoku. Súčasťou práce je aj návrh optimalizovanej simulácie automatu založenej na externej pamäti automatu. Navrhnuté prístupy boli implementované v aplikácii vytvorenej v jazyku Python a experimentálne porovnané z hľadiska efektivity validácie a časovej náročnosti riešenia sudoku. Výsledky ukazujú, že optimalizovaná simulácia automatu výrazne redukuje režijné náklady validácie oproti explicitnej simulácii automatu a klasickým validačným funkciám.","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."]},{"key":"dc:title","label":"Title","values":["Řešení sudoku pomocí automatů"]}]}],"canonical_facts":{"dc:contributor.advisor":["Meduna, Alexandr"],"dc:creator":["Vlček, Adam"],"dc:description.abstract":["Táto práca sa zaoberá riešením sudoku pomocou teórie formálnych jazykov a konečných automatov. Opisuje základné algoritmy používané pri riešení sudoku, najmä spätné vyhľadávanie, spätné vyhľadávanie so šírením obmedzení a simulované žíhanie. Sudoku je formalizované ako dvojrozmerné slovo nad konečnou abecedou a množina správnych riešení je definovaná ako jazyk obrazcov. Hlavnou časťou práce je návrh explicitného štvorcestného automatu určeného na validáciu konfigurácií sudoku. Súčasťou práce je aj návrh optimalizovanej simulácie automatu založenej na externej pamäti automatu. Navrhnuté prístupy boli implementované v aplikácii vytvorenej v jazyku Python a experimentálne porovnané z hľadiska efektivity validácie a časovej náročnosti riešenia sudoku. Výsledky ukazujú, že optimalizovaná simulácia automatu výrazne redukuje režijné náklady validácie oproti explicitnej simulácii automatu a klasickým validačným funkciám.","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."],"dc:identifier.other":["168964"],"dc:identifier.uri":["http://hdl.handle.net/11012/258129"],"dc:language.iso":["sk"],"dc:publisher":["Vysoké učení technické v Brně. Fakulta informačních technologií"],"dc:rights":["Standardní licenční smlouva - přístup k plnému textu bez omezení"],"dc:subject":["sudoku","spätné vyhľadávanie","simulované žíhanie","konečné automaty","štvorcestný automat","formálne jazyky","jazyky obrazcov","validácia sudoku","CSP","Python","backtracking","simulated annealing","finite automata","four-way automaton","formal languages","picture languages","sudoku validation"],"dc:title":["Řešení sudoku pomocí automatů"],"dc:type":["Text"],"thesis:institution_name":["Bc."]},"updated_at":"2026-07-24T01:22:29Z"}