Abstract
The 8-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The more general n-puzzle is a classical problem which can be solved using graph search techniques. The problem of finding the optimal solution is NP-hard. In this paper, we analyze the performance of various informed and uninformed search techniques for finding the optimal solution for a solvable goal state of the 8 puzzle. For using the uninformed search techniques, the problem is converted into a game tree and all of the states are examined till we find the goal. In case of informed search techniques, we do not examine all of the states. Essentially, a search tree which is a component of the game tree is built. In a search tree, we make use of an appropriate heuristic which guides us to take a decision from a current state to the next state in an intelligent manner and hence the state space is significantly reduced resulting in memory and time optimization.
Original language | English |
---|---|
Title of host publication | 2017 Innovations in Power and Advanced Computing Technologies, i-PACT 2017 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Pages | 1-5 |
Number of pages | 5 |
Volume | 2017-January |
ISBN (Electronic) | 9781509056828 |
DOIs | |
Publication status | Published - 02-01-2017 |
Event | 2017 Innovations in Power and Advanced Computing Technologies, i-PACT 2017 - Vellore, India Duration: 21-04-2017 → 22-04-2017 |
Conference
Conference | 2017 Innovations in Power and Advanced Computing Technologies, i-PACT 2017 |
---|---|
Country/Territory | India |
City | Vellore |
Period | 21-04-17 → 22-04-17 |
All Science Journal Classification (ASJC) codes
- Control and Optimization
- Computer Science Applications
- Energy Engineering and Power Technology
- Renewable Energy, Sustainability and the Environment
- Artificial Intelligence
- Computer Networks and Communications