This master’s thesis explores nonogram logic puzzles, with a focus on their characteristics, solution techniques, computational complexity, and the generation of nonograms using a computer algorithm. The main objective was to develop an efficient algorithm for generating nonograms of various difficulty levels and to implement it in the form of a user-friendly computer game.
In the theoretical part, we presented the definition of a nonogram – a type of logic puzzle in which the solver uses logical reasoning and the combination of clues to determine the position of black square cells within a predefined rectangular grid. The clues along the rows and columns indicate the lengths of consecutive blocks of black cells. When solved correctly, the arrangement of black and white cells forms a typically black-and-white image. We also described the origin of nonograms and their key features, such as rules, clue structure, and puzzle variations. Furthermore, we examined the computational complexity of solving nonograms and confirmed that the problem is NP-complete. We described various manual solution techniques, such as simple boxes, simple spaces, forcing, glue, joining and splitting, punctuating, mercury, contradiction, and multiple rows. We also presented several automatic techniques, including depth-first search, genetic algorithms, integer programming, iterative approach, and reinforcement learning. The automatic techniques were categorized according to their computational complexities, and their strengths and limitations were discussed.
In the empirical part, we developed a custom algorithm for generating nonograms with predefined difficulty, which was integrated into a computer game. The algorithm generates nonograms of different sizes (5×5, 10×10, 15×15, 20×20, and 25×25) and with varying levels of black cell density (fillRate parameter). A key feature of the algorithm is the verification that each generated nonogram has a unique solution, as only such puzzles are considered well-formed and solvable without guessing. Uniqueness was ensured using a SAT solver, which confirms the logical consistency of the puzzle and excludes unsolvable or ambiguous cases. The game was developed using the Unity engine and the C# programming language. We carried out thorough testing and user evaluation of the game, focusing on the correctness of the generated nonograms and overall user experience.
The results showed that the developed algorithm is efficient, stable, and suitable for generating nonograms with predefined difficulty levels and unique solutions. The evaluation of the game confirmed a clear user interface and showed that the game is motivating and appealing to a wide range of users. The thesis thus successfully combined theoretical foundations with practical application and confirmed the educational potential of nonograms in a learning environment.
|
