Nonogram-ristikoiden ratkaisu syvyyshaulla

Abstract

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.