Nonogrami

magistrsko delo

Aljaž Ferk (Author), Andrej Taranenko (Mentor)

Abstract

Nonogram je uganka, s katero lahko ob njenem reševanju narišemo sliko. Magistrsko delo je namenjeno algoritmičnemu reševanju črno-belih nonogramov. S temi algoritmi lahko preverjamo pravilnost rešitve nonograma in jih lahko uporabljamo tudi kot pomoč pri človeškem reševanju. Najprej je predstavljen algoritem, ki lahko reši le nekatere nonograme, kasneje je ta algoritem nadgrajen tako, da najde vse možne rešitve. Odgovori tudi vprašanje, kako dober je prvoten algoritem ob večanju dimenzij naključnih nonogramov. Predstavimo tudi hiter način barvanja kotov nekaterih nonogramov. Na koncu je predstavljen tudi vpliv nekaterih komponent na čas reševanja nonograma.

Keywords

magistrska dela;nonogram;Chernoffova meja;

Data

Language:	Slovenian
Year of publishing:	2022
Typology:	2.09 - Master's Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[A. Ferk]
UDC:	51:793.7(043.2)
COBISS:	127463427
Views:	4
Downloads:	1
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Nonograms
Secondary abstract:	A nonogram is a puzzle, with which we can draw a picture, while solving it. The thesis provides algorithmic solutions to black-and-white nonograms. With these algorithms we can check the correctness of the nonogram's solutions, and we can also use them as an aid for human solving. First, an algorithm is presented that can solve only some nonograms, and later on this algorithm is improved so it finds all possible solutions. The question of how good the first algorithm is when increasing the dimensions of random nonograms is also answered. A quick way to paint the corners of some nonograms is also presented. Lastly, the influence of some components on the time it takes to solve a nonogram puzzle is presented.
Secondary keywords:	master theses;nonogram;Chernoff bound;Algoritmi;Naloge, vaje itd.;Univerzitetna in visokošolska dela;
Type (COBISS):	Master's thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	55 str.
ID:	15955275