Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Tvorjenje logičnih ugank tipa nonogram [Elektronski vir] = Generation of nonograms : magistrsko delo
    Zavrl, Laura
    V magistrskem delu smo obravnavali logične uganke tipa nonogram, pri čemer smo se osredotočili na njihove značilnosti, tehnike reševanja, računsko zahtevnost ter tvorjenje nonogramov s pomočjo ... računalniškega algoritma. Glavni cilj je bil razviti učinkovit algoritem za tvorjenje nonogramov različnih težavnostnih stopenj ter ga implementirati v obliki uporabniško prijazne računalniške igre. V teoretičnem delu smo predstavili definicijo nonograma – to je tip logične uganke, pri kateri z logičnim sklepanjem in kombiniranjem namigov ugotavljamo, kje v vnaprej podani pravokotni mreži ležijo črna kvadratna polja. Namigi ob mreži predstavljajo dolžine sklopov zaporednih črnih polj v vsaki vrstici in stolpcu. Ob pravilni rešitvi, črna in bela polja v mreži tvorijo neko sliko, ki je običajno črno-bela. Opisali smo tudi njegovo poreklo ter temeljne značilnosti, kot so pravila, struktura namigov in različne oblike uganke. Podrobneje smo raziskali računsko zahtevnost reševanja nonogramov in ugotovili, da gre za NP-poln problem. Opisali smo različne manualne tehnike reševanja, kot so preprosta polja, preprosta bela polja, prisilna bela polja, lepilo, združevanje in ločevanje, prekinitev, živo srebro, protislovje ter večvrstično reševanje. Prav tako smo opisali nekatere avtomatske tehnike, kot so iskanje v globino, genetski algoritmi, celoštevilsko programiranje, iterativni pristop in spodbujevalno učenje. Avtomatske tehnike smo glede na računsko zahtevnost razvrstili v kategorije in predstavili njihove prednosti ter omejitve. V empiričnem delu smo razvili lasten algoritem za tvorjenje nonogramov z vnaprej določeno težavnostjo, ki smo ga integrirali v računalniško igro. Algoritem generira nonograme različnih velikosti (5×5, 10×10, 15×15, 20×20 in 25×25) in z različnimi stopnjami zapolnitve s črnimi polji (parameter fillRate). Ključni del algoritma je preverjanje, da ima vsak ustvarjen nonogram enolično rešitev, saj so le taki nonogrami pravilno oblikovani in rešljivi brez ugibanja. Enoličnost smo zagotovili s pomočjo SAT-reševalnika, ki potrdi logično skladnost uganke in izloči vse nerešljive ali dvoumne primere. Pri razvoju igre smo uporabili okolje Unity in programski jezik C#. Izvedli smo temeljito testiranje in evalvacijo igre z uporabniki, pri čemer smo preverili pravilnost generiranih nonogramov ter uporabniško izkušnjo. Rezultati so pokazali, da je razvit algoritem učinkovit, stabilen ter primeren za tvorjenje nonogramov z določeno težavnostjo in enolično rešitvijo. Evalvacija igre je potrdila, da je uporabniški vmesnik jasen, igra pa motivacijska in privlačna za različne skupine uporabnikov. Magistrsko delo je tako uspešno povezalo teoretične temelje in praktično uporabnost ter potrdilo pedagoški potencial nonogramov v izobraževalnem okolju.
    Vrsta gradiva - magistrsko delo ; neleposlovje za odrasle
    Založništvo in izdelava - Ljubljana : [L. Zavrl], 2025
    Jezik - slovenski
    COBISS.SI-ID - 242562563

    Povezava(-e):

    Repozitorij Univerze v Ljubljani – RUL

Vnos na polico