2.
Objective:
i. To understand and implement Best First Search for solving the 8-puzzle problem.
ii. To use a heuristic function (Manhattan Distance) to guide the search efficiently.
iii. To observe how heuristic-based search differs from uninformed methods like BFS, DFS.
iv. To analyze how Best First Search reduces unnecessary state exploration and reaches the
goal faster.
3. Necessary Materials and Software:
i. Python 3.10 was installed and used for the experiment.
ii. The program was developed and executed in Visual Studio Code (VS Code).
iii. The code can run on any major operating system, including Windows, macOS, or Linux.
• Working Procedure:
i. Initialization: Start the algorithm.
ii. Configuration: Define the starting (initial) state and the target (goal) configuration of the $3 \
times 3$ board.
iii. Data Structure Setup: Initialize a Priority Queue to manage board states based on their
heuristic scores and a Visited Set to keep track of explored configurations, preventing infinite
loops.
iv. Initial Evaluation: Calculate the heuristic value (Manhattan Distance) for the starting board
and insert it into the priority queue.
v. Search Execution: Enter the main search loop. If the priority queue becomes empty before the
goal is reached, terminate and report that no solution exists
• 5. Flow Chart:
resulting in a more direct and computationally efficient path to the solution.
• 7. Discussion:
This experiment illustrates the power of Informed Search over traditional uninformed methods
like DFS or BFS. While uninformed strategies explore nodes based on depth or breadth, Best
First Search utilizes a heuristic function to "guide" the search. In our implementation, the
Manhattan Distance served as this guide, estimating the remaining distance to the goal by
summing the absolute differences of tile [Link] core advantage of Best First Search lies in
its efficiency. By focusing on states that "appear" most promising, it avoids exploring vast,
irrelevant branches of the search tree. The integration of a visited set further optimized the
process by preventing cycles and redundant [Link], it is important to note a key
characteristic: Best First Search is greedy. Because it only considers the estimated cost to the
goal and ignores the cost already incurred to reach the current state it does not always guarantee
the mathematically shortest path (optimal solution). Despite this, the experiment confirms that
for problems like the 8-puzzle, it offers a superior balance between speed and simplicity
compared to blind search techniques.
• 8. Conclusion:
The experiment successfully achieved its objective of solving the 8-puzzle problem through the
Best First Search algorithm. The results clearly demonstrate that incorporating domain-specific
knowledge—via the Manhattan Distance heuristic—allows an agent to explore the state space
more intelligently than basic search methods.
Furthermore, this study provides a vital foundation for understanding more sophisticated
algorithms, such as A Search*, which combines both path cost and heuristic estimation. Overall,
the experiment enhanced our practical understanding of informed search strategies, heuristic
evaluation, and their critical role in solving complex Artificial Intelligence problems.
9. Source Code:
import copy
import heapq
N=3
class p8_board:
def __init__(self, board, x, y, depth, parent=None, h=0):
[Link] = board
self.x = x
self.y = y
[Link] = depth
[Link] = parent
self.h = h
def __lt__(self, other):
return self.h < other.h
row_moves = [0, 0, -1, 1]
col_moves = [-1, 1, 0, 0]
def is_valid(x, y):
return 0 <= x < N and 0 <= y < N
def is_goal(board):
goal = [[1, 2, 3],
[4, 5, 6],
[7, 8, 0]]
return board == goal
def manhattan_distance(board):
distance = 0
for i in range(N):
for j in range(N):
if board[i][j] != 0:
goal_x = (board[i][j] - 1) // N
goal_y = (board[i][j] - 1) % N
distance += abs(i - goal_x) + abs(j - goal_y)
return distance
def best_first_search(start_board, x, y):
pq = []
visited = set()
h = manhattan_distance(start_board)
start_node = p8_board(start_board, x, y, 0, None, h)
[Link](pq, start_node)
[Link](tuple(map(tuple, start_board)))
while pq:
current = [Link](pq)
if is_goal([Link]):
prints(current)
return
for i in range(4):
new_x = current.x + row_moves[i]
new_y = current.y + col_moves[i]
if is_valid(new_x, new_y):
new_board = [Link]([Link])
new_board[current.x][current.y], new_board[new_x][new_y] = \
new_board[new_x][new_y], new_board[current.x][current.y]
board_tuple = tuple(map(tuple, new_board))
if board_tuple not in visited:
[Link](board_tuple)
h = manhattan_distance(new_board)
[Link](pq,p8_board(new_board, new_x, new_y,[Link] + 1, current, h))
print("NO solution found")
def prints(node):
path = []
while node:
[Link](node)
node = [Link]
[Link]()
for i, step in enumerate(path):
print(f"Step {i}")
for row in [Link]:
print(row)
print()
if __name__ == "__main__":
start = [[1, 4, 6],
[8, 0, 2],
[3, 7, 5]]
x, y = 1, 1
print("Solving with Best First Search (Manhattan Distance)...")
best_first_search(start, x, y)