Nonogram-ristikoiden ratkaisu syvyyshaulla

Tutkielman aiheena on tutkia japanilaisten ristikoiden eli nonogrammien ratkaisua syvyyshakualgoritmia käyttäen. Nonogram on Japanissa 1990-luvulla kehitetty pulmapeli, jossa on tarkoituksena värittää ristikon ruutuja rivi- ja sarakevihjeiden avulla erilaisia ratkaisumenetelmiä hyödyntäen. Nonogram-...

Täydet tiedot

Bibliografiset tiedot
Päätekijä: Leskelä, Jesse
Muut tekijät: Informaatioteknologian tiedekunta, Faculty of Information Technology, Informaatioteknologia, Information Technology, Jyväskylän yliopisto, University of Jyväskylä
Aineistotyyppi: Kandityö
Kieli:fin
Julkaistu: 2023
Aiheet:
Linkit: https://jyx.jyu.fi/handle/123456789/87069
_version_ 1826225815938924544
author Leskelä, Jesse
author2 Informaatioteknologian tiedekunta Faculty of Information Technology Informaatioteknologia Information Technology Jyväskylän yliopisto University of Jyväskylä
author_facet Leskelä, Jesse Informaatioteknologian tiedekunta Faculty of Information Technology Informaatioteknologia Information Technology Jyväskylän yliopisto University of Jyväskylä Leskelä, Jesse Informaatioteknologian tiedekunta Faculty of Information Technology Informaatioteknologia Information Technology Jyväskylän yliopisto University of Jyväskylä
author_sort Leskelä, Jesse
datasource_str_mv jyx
description Tutkielman aiheena on tutkia japanilaisten ristikoiden eli nonogrammien ratkaisua syvyyshakualgoritmia käyttäen. Nonogram on Japanissa 1990-luvulla kehitetty pulmapeli, jossa on tarkoituksena värittää ristikon ruutuja rivi- ja sarakevihjeiden avulla erilaisia ratkaisumenetelmiä hyödyntäen. Nonogram-ristikoiden ratkaisu on NP-täydellinen ongelma, joten tehokasta polynomisessa ajassa ja kaikille ristikoille toimivaa ratkaisualgoritmia ei ole löydetty. Tutkielmassa esitetään syvyyshakualgoritmin lisäksi vihjeisiin perustuva ratkonta- algoritmi sekä simuloitua jäähdytystä hyödyntävä algoritmi. Tutkielman lopussa vertaillaan eri julkaisuissa saatuja ratkontatuloksia edellä mainittujen algoritmien lisäksi myös näiden yhdistelmien osalta. Tutkimusten perusteella voidaan havaita, että syvyyshakumenetelmä löytää aina ratkaisun mille tahansa ristikolle, mutta kyseinen menetelmä on erittäin hidas ristikon koon kasvaessa. Simuloitu jäähdytys toimii vastaavasti hyvin pienillä ristikoilla, mutta ristikon koon kasvaessa suoritusaika kasvaa eksponentiaalisesti. Vihjeiden avulla ratkominen onnistuu polynomisessa ajassa, mutta arvaamista vaativissa ristikoissa kyseinen menetelmä ei pysty löytämään kokonaista ratkaisua. Tällaisissa tapauksissa vihjeratkojien ja esimerkiksi syvyyshakualgoritmien yhdistelyn todettiin tuottavan hyviä tuloksia jopa suurten ristikoiden ratkaisussa. The aim of this thesis is to examine the solving process of japanese puzzles known as nonograms using depth-first search. Nonogram is a puzzle game invented in Japan in the 1990’s, and the aim of the game is to color squares in a grid based on the given row and column hints. Solving nonogram puzzles is an NP-complete problem, which means that no efficient algorithm exists that can solve all puzzles in polynomial time. In addition to the depth-first search algorithm, this thesis presents an algorithm, often called a line solver, that uses row and column hints to solve the puzzle as well as an algorithm that uses simulated annealing to find a solution. The final part focuses on the results gathered from different publications regarding the solving time and efficiency of the aforementioned algorithms as well as their combined uses. The results indicate that depth-first search will always find a solution for any given puzzle but the execution time will increase rapidly in conjunction with puzzle size. Simulated annealing works well with smaller puzzles, but the execution time increases exponentially as puzzle size increases. Line solvers can solve puzzles in polynomial time but cannot find a complete solution should guessing be required to advance the solving process. In such cases combining line solvers and other algorithms, depth-first search for instance, produced commendable results even on larger puzzles.
first_indexed 2023-05-22T20:01:00Z
format Kandityö
free_online_boolean 1
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"}]
id jyx.123456789_87069
language fin
last_indexed 2025-02-18T10:54:27Z
main_date 2023-01-01T00:00:00Z
main_date_str 2023
online_boolean 1
online_urls_str_mv {"url":"https:\/\/jyx.jyu.fi\/bitstreams\/757b393d-c952-4756-90cc-38a59dad2f2b\/download","text":"URN:NBN:fi:jyu-202305223143.pdf","source":"jyx","mediaType":"application\/pdf"}
publishDate 2023
record_format qdc
source_str_mv jyx
spellingShingle Leskelä, Jesse Nonogram-ristikoiden ratkaisu syvyyshaulla nonogram japanilainen ristikko ratkaiseminen syvyyshaku Tietotekniikka Mathematical Information Technology 602 ongelmanratkaisupelit algoritmit tietotekniikka suorituskyky värittäminen
title Nonogram-ristikoiden ratkaisu syvyyshaulla
title_full Nonogram-ristikoiden ratkaisu syvyyshaulla
title_fullStr Nonogram-ristikoiden ratkaisu syvyyshaulla Nonogram-ristikoiden ratkaisu syvyyshaulla
title_full_unstemmed Nonogram-ristikoiden ratkaisu syvyyshaulla Nonogram-ristikoiden ratkaisu syvyyshaulla
title_short Nonogram-ristikoiden ratkaisu syvyyshaulla
title_sort nonogram ristikoiden ratkaisu syvyyshaulla
title_txtP Nonogram-ristikoiden ratkaisu syvyyshaulla
topic nonogram japanilainen ristikko ratkaiseminen syvyyshaku Tietotekniikka Mathematical Information Technology 602 ongelmanratkaisupelit algoritmit tietotekniikka suorituskyky värittäminen
topic_facet 602 Mathematical Information Technology Tietotekniikka algoritmit japanilainen ristikko nonogram ongelmanratkaisupelit ratkaiseminen suorituskyky syvyyshaku tietotekniikka värittäminen
url https://jyx.jyu.fi/handle/123456789/87069 http://www.urn.fi/URN:NBN:fi:jyu-202305223143
work_keys_str_mv AT leskeläjesse nonogramristikoidenratkaisusyvyyshaulla