Undergraduate YPEC 2021

UG13-A Game Generator for Sliding Puzzles

A sliding puzzle, or sliding block game, is a very interesting and challenging game. It requires players to move one block horizontally or vertically without overlapping or crossing the game board in each step. The main target is to use as few steps as possible to reach an end configuration. Over the past few years, it has been proved that finding solutions to some sliding puzzles is an NP-hard problem, and some research work has been done to figure out solutions to all kinds of sliding puzzles. However, little work pays attention to developing an intelligent and compatible system that can automatically generate a series of sliding puzzles. In this project, a novel game generator for sliding puzzles is designed and implemented, producing different types of complex sliding puzzles with optimal solutions. In general, this powerful system is composed of three main components: (1) a pivotal algorithm that can conduct a complete search on configurations of various sliding puzzles and generate the corresponding game codes; (2) a compatible game framework that defines game logic of several sliding puzzles and can render the generated puzzles in real time; (3) an image interpreter that can process the image input, i.e., a hand-painted puzzle, and convert it into a numerical matrix in the pre-defined format of the pivotal algorithm’s input. Overall, plenty of methods and techniques are utilized, including the multi-source Breadth-First Search, fast hash operations, and image processing. As a result, a powerful game generator is achieved for generating three kinds of complex sliding puzzles with optimal solutions, i.e., Kltoski, 15-puzzle, and Sokoban. Besides, a complete search on Klotski is successfully carried out, generating the most complicated Klotski puzzle games. Additionally, it provides users with a platform to design and produce diverse sliding puzzles by processing and reading information from pictorial or text inputs.