8-Puzzle-Solver

8 Puzzle solver using different search functions as DFS, BFS and A*.

Table of Content

• 8-Puzzle-Solver
  • Deployment
  • Data Structure Used
    • DFS
    • BFS
    • A*
  • State Representation
  • Algorithms Used
    • BFS
    • DFS
    • A*
      • Heuristic Functions
        • Manhattan Distance
        • Euclidean Distance
        • Which One is better?
  • Analysis for Different Algorithms.
  • Graphical Interface
  • Contributors

Deployment

• The project was built using Python 3.9, make sure you configure your python interpreter correctly
• You should run the "interface.py" python file inside the "GUI" folder, you can do that by running the following command inside the "GUI" folder

 python interface.py

Data Structure Used

DFS

• Stack to store the states in frontier
• Hash Map to check if the state is either in frontier or explored or not
• Hash Map to get the parent of each state (used to get path)
• Hash Map to get the cost of each state

BFS

• Queue to store the states in frontier
• Hash Map to check if the state is either in frontier or explored or not
• Hash Map to get the parent of each state (used to get path)
• Hash Map to get the cost of each state

A*

• Priority Queue to store the states in frontier
• Hash Map to check if the state is explored or not
• Hash Map to get the parent of each state (used to get path)
• Hash Map to get the cost of each state

State Representation

• The state is represented as a single number starting from first row and first column as the most significant digit, and the bottom right as least significant digit, so the following state is represented as the number "102345678"

1	0	2
3	4	5
6	7	8

• The state is stored as integer to reduce the amount of space the application uses, integer is stored in 4 bytes while storing the state as string would cost 9 bytes.
• The state is then converted to a string to be easily proccessed.
• Getting string representation of a state is done through a simple function

  def getStringRepresentation(x):
      if(int(math.log10(x))+1 == 9):
          return str(x)
      else :
          return "0"+str(x)   

• Getting the next possible states is done throught a simple algorithm which goes as follows
  • Convert the index of character "0" in state to 2D index

    idx = state.index('0')
    i = int(idx / 3)
    j = int(idx % 3)

  • Get the possible moves in all 4 directions

    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    for x in range(0, 4):
        nx = i + dx[x]
        ny = j + dy[x]

  • Check if the new 2D index is a valid index

    def checkValid(nx, ny):
    if nx >= 3 or nx < 0 or ny >= 3 or ny < 0:
        return 0
    return 1

  • Convert the index of possible moves to 1D

    nwIdx = int(nx * 3 + ny)

  • The next state is a new string where charachter "0" and the charachter at the new index are swapped

Algorithms Used

BFS

• The Pseudo Code is as follows

DFS

• The Pseudo Code is as follows

A*

• The Pseudo Code is as follows

Heuristic Functions

• The heuristic functions are used in A* search to give a priority to each state to make the "probably" best state to be explored first.

Manhattan Distance

• It is the sum of absolute values of differences in the goal’s x and y coordinates and the current cell’s x and y coordinates respectively, the function value for each state is done through a simple function

def getManhattanDistance(state):
    sum = 0
    for i in range(1, 9):
        goalX = int(i / 3)
        goalY = i % 3
        idx = state.index(str(i))
        itemX = int(idx / 3)
        itemY = idx % 3
        sum += (abs(goalX - itemX) + abs(goalY - itemY))
    return sum

Euclidean Distance

• It is the distance between the current cell and the goal cell using the following formula

  

• The value of Euclidean Distance function for each state is done through this function

def getEuclideanDistance(state):
    sum = 0
    for i in range(1, 9):
        goalX = int(i / 3)
        goalY = i % 3
        idx = state.index(str(i))
        itemX = int(idx / 3)
        itemY = idx % 3
        sum += math.sqrt(pow((goalX - itemX), 2) + pow((goalY - itemY), 2))
    return sum

Which One is better?

• Both of the heuristic functions used are admissible, but we want to know which one of them is better and more effiecient
• According to the analysis done in Analysis Section, Manhatten Distance is a better admissible function at it expands less number of states than Euclidean Distance. That will result in making the values of Manhatten Distance function values closer to the optimal function much more than the Euclidean Distance.

Analysis for Different Algorithms.

• For the following random test case:

7	0	2
8	5	3
6	1	4

Algorithm	Cost of Path	Nodes Expanded	Search Depth	Running time
BFS	27	174386	27	1.27s
DFS	54497	63397	54497	0.29s
A* Manhattan	27	3495	27	0.07s
A* Euclidean	27	11639	27	0.513s

• In the last test case, the DFS algorithm was lucky enough to have search depth = cost of path, usually the algorithm will have higher search depth than cost of path.

Graphical Interface

Contributors

1- Yousef Kotp

2- Adham Mohammed

3- Mohammed Farid