Nonogram-ristikoiden ratkaisu syvyyshaulla - Leskelä, Jesse (2023)
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.