Řešení sudoku pomocí automatů

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.

Grantor dc:publisher

Vysoké učení technické v Brně. Fakulta informačních technologií

Author dc:creator

• Vlček, Adam

Advisor dc:contributor.advisor

• Meduna, Alexandr

• 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

Statement dc:rights

• Standardní licenční smlouva - přístup k plnému textu bez omezení

Language dc:language.iso

sk

Dc Identifier Other

168964

OAI identifier oai:identifier

oai:dspace.vut.cz:11012/258129