| fullrecord |
[{"key": "dc.contributor.advisor", "value": "Saksa, Tytti", "language": "", "element": "contributor", "qualifier": "advisor", "schema": "dc"}, {"key": "dc.contributor.author", "value": "Leskel\u00e4, Jesse", "language": "", "element": "contributor", "qualifier": "author", "schema": "dc"}, {"key": "dc.date.accessioned", "value": "2023-05-22T10:49:52Z", "language": null, "element": "date", "qualifier": "accessioned", "schema": "dc"}, {"key": "dc.date.available", "value": "2023-05-22T10:49:52Z", "language": null, "element": "date", "qualifier": "available", "schema": "dc"}, {"key": "dc.date.issued", "value": "2023", "language": "", "element": "date", "qualifier": "issued", "schema": "dc"}, {"key": "dc.identifier.uri", "value": "https://jyx.jyu.fi/handle/123456789/87069", "language": null, "element": "identifier", "qualifier": "uri", "schema": "dc"}, {"key": "dc.description.abstract", "value": "Tutkielman aiheena on tutkia japanilaisten ristikoiden eli nonogrammien ratkaisua syvyyshakualgoritmia k\u00e4ytt\u00e4en. Nonogram on Japanissa 1990-luvulla kehitetty pulmapeli, jossa on tarkoituksena v\u00e4ritt\u00e4\u00e4 ristikon ruutuja rivi- ja sarakevihjeiden avulla erilaisia\nratkaisumenetelmi\u00e4 hy\u00f6dynt\u00e4en. Nonogram-ristikoiden ratkaisu on NP-t\u00e4ydellinen ongelma,\njoten tehokasta polynomisessa ajassa ja kaikille ristikoille toimivaa ratkaisualgoritmia ei ole\nl\u00f6ydetty. Tutkielmassa esitet\u00e4\u00e4n syvyyshakualgoritmin lis\u00e4ksi vihjeisiin perustuva ratkonta-\nalgoritmi sek\u00e4 simuloitua j\u00e4\u00e4hdytyst\u00e4 hy\u00f6dynt\u00e4v\u00e4 algoritmi. Tutkielman lopussa vertaillaan\neri julkaisuissa saatuja ratkontatuloksia edell\u00e4 mainittujen algoritmien lis\u00e4ksi my\u00f6s n\u00e4iden\nyhdistelmien osalta.\n\nTutkimusten perusteella voidaan havaita, ett\u00e4 syvyyshakumenetelm\u00e4 l\u00f6yt\u00e4\u00e4 aina ratkaisun\nmille tahansa ristikolle, mutta kyseinen menetelm\u00e4 on eritt\u00e4in hidas ristikon koon kasvaessa.\nSimuloitu j\u00e4\u00e4hdytys toimii vastaavasti hyvin pienill\u00e4 ristikoilla, mutta ristikon koon kasvaessa suoritusaika kasvaa eksponentiaalisesti. Vihjeiden avulla ratkominen onnistuu polynomisessa ajassa, mutta arvaamista vaativissa ristikoissa kyseinen menetelm\u00e4 ei pysty l\u00f6yt\u00e4m\u00e4\u00e4n\nkokonaista ratkaisua. T\u00e4llaisissa tapauksissa vihjeratkojien ja esimerkiksi syvyyshakualgoritmien yhdistelyn todettiin tuottavan hyvi\u00e4 tuloksia jopa suurten ristikoiden ratkaisussa.", "language": "fi", "element": "description", "qualifier": "abstract", "schema": "dc"}, {"key": "dc.description.abstract", "value": "The aim of this thesis is to examine the solving process of japanese puzzles known\nas nonograms using depth-first search. Nonogram is a puzzle game invented in Japan in the\n1990\u2019s, and the aim of the game is to color squares in a grid based on the given row and\ncolumn hints. Solving nonogram puzzles is an NP-complete problem, which means that no\nefficient algorithm exists that can solve all puzzles in polynomial time. In addition to the\ndepth-first search algorithm, this thesis presents an algorithm, often called a line solver, that\nuses row and column hints to solve the puzzle as well as an algorithm that uses simulated\nannealing to find a solution. The final part focuses on the results gathered from different\npublications regarding the solving time and efficiency of the aforementioned algorithms as\nwell as their combined uses.\n\nThe results indicate that depth-first search will always find a solution for any given puzzle but\nthe execution time will increase rapidly in conjunction with puzzle size. Simulated annealing\nworks well with smaller puzzles, but the execution time increases exponentially as puzzle\nsize increases. Line solvers can solve puzzles in polynomial time but cannot find a complete\nsolution should guessing be required to advance the solving process. In such cases combining\nline solvers and other algorithms, depth-first search for instance, produced commendable\nresults even on larger puzzles.", "language": "en", "element": "description", "qualifier": "abstract", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Submitted by Paivi Vuorio (paelvuor@jyu.fi) on 2023-05-22T10:49:52Z\nNo. of bitstreams: 0", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Made available in DSpace on 2023-05-22T10:49:52Z (GMT). No. of bitstreams: 0\n Previous issue date: 2023", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.format.extent", "value": "22", "language": "", "element": "format", "qualifier": "extent", "schema": "dc"}, {"key": "dc.language.iso", "value": "fin", "language": null, "element": "language", "qualifier": "iso", "schema": "dc"}, {"key": "dc.rights", "value": "In Copyright", "language": "en", "element": "rights", "qualifier": null, "schema": "dc"}, {"key": "dc.subject.other", "value": "nonogram", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "japanilainen ristikko", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "ratkaiseminen", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "syvyyshaku", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.title", "value": "Nonogram-ristikoiden ratkaisu syvyyshaulla", "language": "", "element": "title", "qualifier": null, "schema": "dc"}, {"key": "dc.type", "value": "bachelor thesis", "language": null, "element": "type", "qualifier": null, "schema": "dc"}, {"key": "dc.identifier.urn", "value": "URN:NBN:fi:jyu-202305223143", "language": "", "element": "identifier", "qualifier": "urn", "schema": "dc"}, {"key": "dc.type.ontasot", "value": "Bachelor's thesis", "language": "en", "element": "type", "qualifier": "ontasot", "schema": "dc"}, {"key": "dc.type.ontasot", "value": "Kandidaatinty\u00f6", "language": "fi", "element": "type", "qualifier": "ontasot", "schema": "dc"}, {"key": "dc.contributor.faculty", "value": "Informaatioteknologian tiedekunta", "language": "fi", "element": "contributor", "qualifier": "faculty", "schema": "dc"}, {"key": "dc.contributor.faculty", "value": "Faculty of Information Technology", "language": "en", "element": "contributor", "qualifier": "faculty", "schema": "dc"}, {"key": "dc.contributor.department", "value": "Informaatioteknologia", "language": "fi", "element": "contributor", "qualifier": "department", "schema": "dc"}, {"key": "dc.contributor.department", "value": "Information Technology", "language": "en", "element": "contributor", "qualifier": "department", "schema": "dc"}, {"key": "dc.contributor.organization", "value": "Jyv\u00e4skyl\u00e4n yliopisto", "language": "fi", "element": "contributor", "qualifier": "organization", "schema": "dc"}, {"key": "dc.contributor.organization", "value": "University of Jyv\u00e4skyl\u00e4", "language": "en", "element": "contributor", "qualifier": "organization", "schema": "dc"}, {"key": "dc.subject.discipline", "value": "Tietotekniikka", "language": "fi", "element": "subject", "qualifier": "discipline", "schema": "dc"}, {"key": "dc.subject.discipline", "value": "Mathematical Information Technology", "language": "en", "element": "subject", "qualifier": "discipline", "schema": "dc"}, {"key": "yvv.contractresearch.funding", "value": "0", "language": "", "element": "contractresearch", "qualifier": "funding", "schema": "yvv"}, {"key": "dc.type.coar", "value": "http://purl.org/coar/resource_type/c_7a1f", "language": null, "element": "type", "qualifier": "coar", "schema": "dc"}, {"key": "dc.rights.accesslevel", "value": "openAccess", "language": null, "element": "rights", "qualifier": "accesslevel", "schema": "dc"}, {"key": "dc.type.publication", "value": "bachelorThesis", "language": null, "element": "type", "qualifier": "publication", "schema": "dc"}, {"key": "dc.subject.oppiainekoodi", "value": "602", "language": "", "element": "subject", "qualifier": "oppiainekoodi", "schema": "dc"}, {"key": "dc.subject.yso", "value": "ongelmanratkaisupelit", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "algoritmit", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "tietotekniikka", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "suorituskyky", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "v\u00e4ritt\u00e4minen", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.rights.url", "value": "https://rightsstatements.org/page/InC/1.0/", "language": null, "element": "rights", "qualifier": "url", "schema": "dc"}]
|