Orodje za vizualizacijo delovanja algoritmov pri reševanju problemov Sokoban

Makovec, Anei (author), Guid, Matej (mentor)

Igra Sokoban ponuja računsko zahtevne in težko rešljive probleme. Obstaja kopica algoritmov, ki jih je moč uporabiti za reševanje teh problemov, a nobenemu od njih ne uspe rešiti prav vseh, četudi morda na videz relativno enostavnih problemov Sokoban. Igra Sokoban tako predstavlja izvrstno domeno za izpopolnjevanje preiskovalnih algoritmov, hkrati pa nam lahko pomaga izboljšati njihovo razumevanje. V diplomskem delu bomo predstavili aplikacijo, ki služi bodisi kot orodje za pomoč pri razvoju omenjenih algoritmov bodisi kot sredstvo za analizo in poučevanje njihovega delovanja. Predstavili bomo razvoj omenjene aplikacije, preizkusili njeno delovanje na praktičnih problemih Sokoban in pokazali, da deluje pravilno ter da je relevantna za uporabo.

• Language: Slovenian
• Keywords: Sokoban, aplikacija, vizualizacija, reševanje problema, algoritmi.
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2019
• PID: 20.500.12556/RUL-107093
• Publication date in RUL: 27.03.2019

Secondary language

• Language: English
• Title: A tool for visualizing the functionality of algorithms for solving Sokoban puzzles

Abstract

Sokoban is a puzzle game that offers computationally complex problems that are very difficult to solve. There are many algorithms that can be used to solve these problems, but none is successful in solving all given, even relatively simple problems. Therefore, the game Sokoban is an interesting platform both for the improvement of the search algorithms and for a better understanding. In this thesis we propose an application that can be used both as a tool to support the developers of these algorithms, or as a means to analyze and teach their functioning. We present the development process of the application, test its functionality on practical Sokoban puzzles and show that it works correctly and is a relevant tool.

• Keywords: Sokoban, application, visualization, problem solving, algorithms.