Analysis and Implementation of Admissible Heuristics in 8 Puzzle Problem

Nayak, Debasish (2014) Analysis and Implementation of Admissible Heuristics in 8 Puzzle Problem. BTech thesis.



N-puzzle problem has been one of the basic problem since the beginning of artificial intelligence. The most popular version of n-puzzle among people is 8-puzzle problem. It consists of an area divided into 3x3 grid containing 8 numbered (to identify) tiles and one empty grid. We are given an initial state and we have to reach the goal state which is also specified. In this project, we have used various informed search methods like a*algorithm, ida* algorithm to solve the puzzle. Various heuristic involved in the informed search like number of misplaced tiles, Manhattan distance were analyzed; Manhattan distance being one of the most popular ones. Drawbacks of the heuristics are mentioned and an improvement in Manhattan distance heuristic is implemented.

Item Type:Thesis (BTech)
Uncontrolled Keywords:N-puzzle,heuristic function,A star algorithm,Manhattan distance,linear conflict
Subjects:Engineering and Technology > Computer and Information Science > Data Mining
Divisions: Engineering and Technology > Department of Computer Science
ID Code:5575
Deposited By:Hemanta Biswal
Deposited On:18 Jul 2014 15:05
Last Modified:18 Jul 2014 15:05
Supervisor(s):Majhi, B

Repository Staff Only: item control page