Skip to content

Latest commit

 

History

History
232 lines (213 loc) · 7.2 KB

README.md

File metadata and controls

232 lines (213 loc) · 7.2 KB
Raw

8-Puzzle-Solver

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

Table of Content

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

    image

  • 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

image

Contributors

1- Yousef Kotp

2- Adham Mohammed

3- Mohammed Farid