Základné informácie
Autor: Erik Korbeľ
Kontakt: korbel6@uniba.sk
Názov: Algoritmus X pri riešení drevených hlavolamov
Školiteľ: RNDr. Peter Borovanský, PhD.
Autor: Erik Korbeľ
Kontakt: korbel6@uniba.sk
Názov: Algoritmus X pri riešení drevených hlavolamov
Školiteľ: RNDr. Peter Borovanský, PhD.
Cieľom práce je použiť Knuthov Algoritmus X primárne určený na riešenie problému Exact Cover Set problému pri hľadaní riešení netriválnych drevených hlavolamov a skladačiek, napr. z hry Ubongo. Cieľom práce je pomocou tohoto algoritmu navrhnúť mieru náročnosti pre človeka a následne navrhnúť aj veľmi ťažké zadania podobnej hry. Práca predpokladá pochopenie algoritmu X, testovanie na netriviálnych zadaniach a hľadanie limitov tohoto algoritmu pre existujúce drevené hlavolamy. Ďalším cieľom práce je vizualizovať algoritmom nájdené riešenie v nejakom grafickom prostredí.
do 24.11 zbieranie zdrojov
do 30.11 vytvorenie prezentácie zdrojov
do 5.12 nájdenie typov hlavolamov, ktoré bude algoritmus riešiť
do 10.12 začiatie navrhovania kostry aplikácie
do 5.1 hotový funkčný prototyp aplikácie (implentácia dancing links a algoritmus, ktorý je schopní riešiť hlavolamy založené na probléme Exact Cover Set)
do 15.1 napísanie 10 strán textu bakalárskej práce
do 2.2 hotové generovanie hlavolamov pre algoritmus a ich delenie podľa zložitosti riešenia pre človeka
do 10.2 návrh používateľského rozhrania aplikácie
do 10.3 hotové používateľské rozhranie aplikácie
15.3 začatie písania textu práce
do 5.5 napísaný text bakalárskej práce a doladenie všetkých detailov a chýb v kóde aplikácie
14.5. odovzdanie prace
Róbert Mažgut. Analýza algoritmov pre riešenie hry sudoku. Žilinská univerzita v Žiline, 2014.
Mattias Harrysson, Hjalmar Laestander. Solving Sudoku efficiently with Dancing Links. Stockholm, 2014.
Donald E. Knuth. The Art of Computer Programming, Volume 4. Addison-Wesley, 1968.
Donald E. Knuth. Dancing Links. In Millenian Perspectives in Computer Science, pages 187-214, 2000.
Implentácia dancing links v Jave
Android dokumentácia GLSurfaceView
Marcin Moskala, Igor Wojda. Android Development with Kotlin. Packt Publishing Ltd, August 2017.
Naštudoval som si implementáciu Algoritmu X od iných ľudí a prepísal svoj kód ná základe vylepšení, ktoré som tam našiel.
Upravil som implementáciu Algoritmu X podľa princípov clean code.
Naprogramoval triedy, ktoré prekladaju problém drevených hlavolamov do problému Exact cover aby ich mohol riešiť Algoritmus.
Vyskúšal som algoritmus na jednoduchej hre The Genius Square.
Zisťoval som, či moj algoritmus skutočne nájde práve všetky riešenia zadaní hier Genius Square.
Doprogramoval som testovacie funkcie, ktoré dovolia zadať konkrétne zadanie hry, alebo ich vyriešiť všetky.
Implementoval som triedy na formalizáciu zadaní na štýl Ubongo 3D a taktiež testovacie triedy na skúšanie takýchto zadaní.
Refaktoroval som formalizačné triedy, aby boli parametrizované elementárnym dielikom hlavolamu,
teda aby sa jednoduchšie dopĺňala funkcionalita v prípade záujmu o viac dimenzionálne hlavolami.
Vylepšil som testovacie rozhrania, zjednodušil ich. Implementoval rotácie pomocou matíc.
Jemne som upravil implementáciu triedy opisujúce zadanie hlavolamu.
Refaktoroval som triedy Point, Shape a Formalisation tak, aby Shape a Formalisation
boli parametrizované Pointom, ktorý je interface určujúci ako má vyzerať
základná jednotka hlavolamu, teda kód sa dá jednoducho rozšíriť aj o podporu
4D, ND alebo kľudne aj inak tvarovaných hlavolamov.
Oddychoval som a čistil si myseľ.
Mierne som prokrastinoval.
Začal som programovať tvorbu nových zadaní hry Square Game
a odstraňovanie symetrii v hlavolamoch.
Doriešil som problém symetrií riešení.
Spravil som prezentáciu bakalárky.
Začal som zhánať podklady ohľadom použitia OpenGL knižnice
v prostredí Kotlin, na vykreslenie riešení hlavolamov.
Našiel som Kotlin interface pre OpenGL.
Spojazdnil som ho v mojom projekte a
vytvoril printer, ktorý riešenia hlavolamu
vykresluje v 3D podobe pomocou tejto technológie.
K 3D printeru som pridal možnosť otáčania riešení.
Spravil kód, ktorý odstranuje symetrie počas formalizácie.
Spravil som refactor viacerých tried.
V 3D printeri som pridal možnosť priblížiť a oddialiť riešnie, animáciu
zloženia riešenia a tiež možnosť odkliknúť preč ľubovoľný kúsok hlavolamu a
tiež ho vrátiť naspať. Taktiež som pridal kú kockám lemovanie čiernou farbou,
aby boli lepšie odlíšiteľné.
Pohral som sa s možnosťou vylepšenia odstraňovania symetrii fixných tvarov,
bohužiaľ neúspešne. Ošetroval som používateľské vstupy, aby nehrozili nežiadané
vedľajšie účinky.
Vytvoril som triedu, ktorá umožňuje relatívne presne odhadnúť náročnosť
hlavolamu ako číslo medzi 0 a 1, kde 0 je neriešiteľné a 1 je, že má vždy
riešenie. Taktiež som vytvoril generátor nových zadaní pre hru Genius Square
a možnosť testovať užívateľom zadané kocky.
Pridal som generátor Ubongo 3D hier, pričom používateľ si môže zvoliť, či chce easy,
medium, hard alebo impossible hlavolam. Algoritmus takýto hlavolam vygeneruje, overí
jeho zložitosť, vyrieši ho a vykreslí všetky riešenia tohoto hlavolamu.
Premenoval som názvy niektorých tried.
Začal som písať text bakalárskej práce, vytvoril som obsah, pridal úvodné formality a
vložil som tam východiskovú kapitolu, ktorú som začal upravovať.
Doupravoval som východískovú kapitolu.
Napísal som celé kapitoly návrh a implementácia.
Do projektu som doprogramoval benchmark porovnajúci moju implementáciu
Algoritmu X s implementáciami v jave a v C++ a napísal kapitolu o testovaní,
kde opisujem aj výsledky tohto benchmarku.
Napísal som abstrakt, úvod a záver.
Upravil som kapitoly návrh a implementácia podľa pripomienok školiteľa