Introduction

The N-Puzzle problem, also known as the 8-Puzzle or 15-Puzzle, is a classic problem in
artificial intelligence that involves a square grid with numbered tiles. The objective is to
rearrange the tiles from a scrambled initial state to a goal state, typically a predefined
configuration. This problem is a fundamental example of state-space search and is widely used
to test and benchmark various search algorithms.

In this report, we will explore the application of the A* algorithm, an informed search algorithm,
to solve the N-Puzzle problem. We will use the Manhattan Distance heuristic to guide the
search process and optimize the solution. This study aims to provide insights into the
performance and efficiency of A* algorithm in solving the N-Puzzle problem.

Background
Previous Methodologies/Literature Survey
Several methods have been proposed to tackle the N-Puzzle problem, ranging from uninformed
search algorithms like depth-first search and breadth-first search to informed search algorithms
like A* and its variants. Uninformed search algorithms do not use any additional information to
guide their search, while informed search algorithms use heuristics to estimate the cost of
reaching the goal.

A* algorithm, a popular informed search algorithm, is known for its efficiency in finding optimal
solutions while exploring the least number of states. It combines the cost to reach a state (g-
value) and a heuristic estimate of the cost to reach the goal from that state (h-value) to prioritize
states for exploration.

The Manhattan Distance heuristic is commonly used in N-Puzzle problem solving. It calculates
the sum of the horizontal and vertical distances between the current position of each tile and its
goal position. This heuristic provides an estimate of how close a state is to the goal state, which
A* algorithm can use to guide its search efficiently.

Proposed Work
In this study, we propose to solve the N-Puzzle problem using the A* algorithm with the
Manhattan Distance heuristic. We will analyze the performance of this approach by
implementing it on different N-Puzzle instances with varying complexities. The primary
objectives of our work are as follows:
Implement the A* algorithm with the Manhattan Distance heuristic to solve the N-Puzzle
problem.
Evaluate the efficiency of the A* algorithm in finding optimal solutions.
Analyze the computational requirements and time complexity of the algorithm.
Discuss the impact of puzzle complexity on the algorithm's performance.
Methodology
A* Algorithm (Informed Search)
The A* algorithm is an informed search algorithm that explores states in a way that minimizes
the total estimated cost of reaching the goal. It combines the actual cost to reach a state (g-
value) and a heuristic estimate of the cost to reach the goal from that state (h-value) to prioritize
the states for exploration. A* selects states with the lowest f-value, where f(n) = g(n) + h(n).

The algorithm proceeds as follows:

Initialize an open list with the initial state.

While the open list is not empty:
Select the state with the lowest f-value.
Expand the selected state by generating its successor states.
Calculate the f-value for each successor state and add them to the open list.
Continue until the goal state is reached or no more states can be expanded.
Heuristic Value: Calculated using Manhattan Distance
The Manhattan Distance heuristic is calculated by summing the horizontal and vertical
distances between each tile's current position and its goal position. It is a reliable and
admissible heuristic for the N-Puzzle problem, ensuring that the estimated cost to reach the
goal is never overestimated. The heuristic value h(n) for a state n is calculated as follows:

h(n) = Σ |x_goal - x_current| + |y_goal - y_current| for all tiles

This heuristic provides an optimistic estimate of the number of moves required to reach the
goal state, making it suitable for guiding A* search efficiently.

Technologies/Platform/Tools Used
For our implementation and experimentation, we utilized the following technologies and tools:
Programming Language: Python 3.x
Platform: Operating System
Data Structures: Lists, Tuple
Libraries: heapq and sys
Development Environment: IDLE Shell 3.x / Jupyter Notebook
Results & Discussion
In this section, we present the results of our experiments and discuss the performance of the A*
algorithm using the Manhattan Distance heuristic in solving the N-Puzzle problem.
Performance Analysis:
We tested the A* algorithm on various N-Puzzle instances with different complexities, ranging
from 8-Puzzle to 15-Puzzle.

Our experiments included measuring the following parameters:

Optimality:
We verified whether the A* algorithm consistently found optimal solutions for the tested
instances.
Efficiency:
We recorded the time required to solve each puzzle and the number of states expanded during
the search.
Memory Usage:
We analyzed the memory consumption of the algorithm, particularly for larger instances, to
assess its practicality.
Execution Time:
It takes more execution time for larger values N. It takes few seconds for the execution of 8
puzzle problem but execution time is more for 15+ puzzle problem as it uses Manhattan
distance to find the heuristic value which is time consuming.
Impact of Puzzle Complexity:
We examined how the complexity of the puzzle, in terms of the number of tiles and initial state
arrangements, influenced the algorithm's performance.
Optimal Solutions:
Our experiments consistently demonstrated that the A* algorithm with the Manhattan Distance
heuristic produced optimal solutions for all tested N-Puzzle instances. This aligns with the
theoretical guarantees of A* when using an admissible heuristic.
Efficiency:
The A* algorithm proved to be efficient in finding optimal solutions. It exhibited a notable
advantage over uninformed search algorithms like depth-first search, especially for puzzles with
a larger number of states. The algorithm's use of the Manhattan Distance heuristic allowed it to
quickly identify promising paths to the goal state.
Memory Usage:
While A* is memory-intensive compared to some uninformed search algorithms, it performed
well within acceptable memory limits for the N-Puzzle problem. Memory consumption primarily
depends on the size and complexity of the puzzle and the available system resources. In our
experiments, the memory usage remained within reasonable bounds, even for the 15-Puzzle
instances.

Impact of Puzzle Complexity:

The complexity of the N-Puzzle, determined by factors such as the number of tiles, initial state
arrangement, and goal state, significantly affected the performance of the A* algorithm. We
observed the following trends:

Larger puzzles with more tiles and initial state permutations generally required more time to
solve, as expected.
Puzzle instances with more misplaced tiles at the start presented a more challenging search
problem, leading to increased expansion of states.
Puzzle instances with a well-structured initial state, closer to the goal, allowed the A* algorithm
to reach the solution faster with fewer state expansions.

Conclusion & Future Work

In conclusion, our study has demonstrated the effectiveness of the A* algorithm with the
Manhattan Distance heuristic in solving the N-Puzzle problem. The algorithm consistently
produced optimal solutions while maintaining reasonable memory usage and computation time.

Future work in this area could explore the following avenues:

Parallelization: Investigate parallel versions of the A* algorithm to improve the search process
and reduce solving times for larger N-Puzzle instances.

Advanced Heuristics: Evaluate the performance of alternative heuristics and assess their
impact on the efficiency and optimality of the algorithm.

Hybrid Algorithms: Combine A* with other search algorithms to harness the strengths of both
informed and uninformed search methods, further improving efficiency.

Real-world Applications: Apply the N-Puzzle problem and A* algorithm to practical scenarios,
such as pathfinding in robotics, game AI, and optimization problems.

User Interfaces: Develop user-friendly interfaces and visualizations to help users understand
and interact with the N-Puzzle problem, making it more accessible to a wider audience.

Overall, the N-Puzzle problem remains a relevant and challenging task in the field of artificial
intelligence, and further research in this area can contribute to the development of more
efficient and practical search algorithms with applications in various domains.