CE-16.16

Title: 

General N Puzzle Sliding Game We Application

Author(s): 

Yichen Liu

Oral Defence Date: 

12/13/2016

Location: 

TH 434

Committee: 

Profs. James Wong & Ilmi Yoon

Abstract: 

The N-Puzzle is a fascinating research topic and classical single-agent path-finding problems in Artificial Intelligent (AI), one example is dynamic robot path-finding that a robot needs to relocate packages in the plane efficiently. Due to the fact that the N-Puzzle problem is NP-Complete, finding an algorithm that can calculate the optimal solution quickly and efficiently is not guaranteed under advanced modern technology. Nevertheless, a range of possible options are still available to solve many reasonable cases and they are worth to be explored. Many real-world applications of the N-Puzzle, its NP-Completeness, along with the opportunity of exploring and implementing many classical state space search algorithms are the most important aspects that drew my attention to choosing it as my graduate project. This web application project is essentially a puzzle solver for 8-Puzzle and 15-Puzzle in the family of N-Puzzle with different search algorithms implemented in the backend. The algorithms implemented are Breadth-first search, Depth-first search, Depth-limited search, Iterative deepening search, Iterative deepening A* and A* algorithm, as well as the Greedy Best Search algorithm. The front end is a simplified web UI for users to interact with the N-Puzzle solver. This web application hosted on AWS is extensively tested and experimental results are collected. Base on the collected results, a performance analysis and comparisons between algorithms are conducted, furthermore, the strengths and weakness of each algorithm are explored.

Keywords: 

A* search, Best-First Search, Breadth-First Search, Depth-First Search, Depth-Limited search, Iterative deepening search, IDA* search, Manhattan distance, N-Puzzle, Playback

Copyright: 

Yichen Liu