- Report this article
Anshul Pareek
Anshul Pareek
Tech Lead at Wipro Ltd. | 6X Salesforce Certified | 1X Copado Certified | Financial Force (Certinia) | 1X Azure Certified | ❤️ coding| IIT Patna
Published Sep 20, 2023
+ Follow
What is the 8 Puzzle Problem?
An 8 puzzle is a simple game consisting of a 3 x 3 grid/matrix (containing 9 squares). One of the squares is empty. The object is to move squares around into different positions and have the numbers displayed in the "goal state".
You can understand the problem using the below-given initial state and goal state:
INITIAL STATE GOAL STATE 1 2 3 1 2 3 0 4 6 => 4 5 6 7 5 8 7 8 0
We have been given a 3×3 board with 8 tiles or elements (every tile has one number from 1 to 8) and one empty space which we have denoted here with "0". The objective is to place the numbers on tiles to match the final goal state using the empty space. We can slide four adjacent (left, right, above, and below) tiles.We can move "0" to Left, Right, Above, and below only if it's possible.
As in the above situation, we cannot move 0 to left but we can move it to top, Right, Bottom. we can move in all directions only when 0 is in the center.
We need to slide 0 to all the possible places until we find out our result.
In order to solve this problem we have many algorithms but here we will discuss BFS and DFS (Part of Uninformed searches) and will compare which should be used and when.
Breadth First Search (BFS):
What is BFS?
Breadth-first search as the name suggests itself will search breadth-wise to find the shortest path in the graph. BFS is an Uninformed but systematic search algorithm that explores level by level.
How BFS works:
To implement this algorithm, we need to use a Queue data structure that follows the FIFO first in first out methodology. In BFS, one vertex is selected at a time and when it is visited and marked then its adjacent are visited and stored in the queue and the visited one, we can remove from queue if all the adjacent vertices are stored or explored.
In BFS we expand all possible moves from the current state before progressing to the next level, prioritizing solutions at shallower depths.
Does BFS promise Optimal Results:
BFS promises optimal or guaranteed results always as it goes level by level so, the result is sure, but it could lead to more time & and space complexity to reach the goal (Only if it is solvable).
With the help of below diagram, you can see how BFS works :
Depth First Search (DFS):
What Is DFS:
Depth First Search as the name suggests will search depth-wise till the Branch’s maximum depth. If the result not found on the branch’s max depth, then it backtracks and searches another node until reaches to depth and will continue the same until reaches the solution.
How DFS works:
As DFS is an edge-based technique. It uses a Stack data structure as to implement DFS we need to have any data structure which follows LIFO Last in first out and for that Stack is the perfect one. In DFS it first visits vertices and pushes into the stack, and if there are no vertices then it pops out the visited vertices.
Does DFS promise Optimal Results:
DFS does not promise the optimal solution and may encounter infinite loops in certain scenarios. DFS may swiftly traverse deep branches of the search tree while potentially bypassing shorter paths.
Below diagram shows how DFS Finds its Result:
We tried to program and found below given results:
Comparative Analysis:
The result showcases the notable difference between BFS and DFS:
Whilst the algorithm successfully reached its goal state, the Iteration cost achieved by BFS is 6 and the dept is 3. Whereas using DFS iteration cost is 10 and depth is 11, which is significantly higher than BFS. This shows that BFS’s strength in finding shorter solutions, as it systematically explores shallow paths first.
DFS demonstrated a relatively shorter runtime as compared to BFS. The advantage in the runtime must be weighed against the potential for DFS to produce suboptimal or longer paths.
In BFS and DFS there is a conceptual difference BFS builds the tree level by level whereas, DFS builds the tree sub-tree by sub-tree. BFS is more suitable for searching vertices closer to the given source whereas, DFS is more suitable when there are solutions away from the source.
BFS considers all neighbors first and therefore not suitable for decision-making trees used in games or puzzles whereas, DFS is more suitable for game or puzzle problems. We decide, and then explore all paths through this decision. And if this decision leads to a win-win situation, we stop. BFS requires More memory than DFS, so Space complexity is greater than DFS.
Example Intuition with 8-Puzzle:
Imagine we have a single folder in which we could have max 3 folders, each representing a state in the sliding puzzle problem. Our goal is to reach a particular folder (the goal state) from our current root folder(the initial state) using the least number of moves. Let’s relate this to 8 puzzle problems:
BFS Approach:
We decided to explore folders in a systematic manner. We start by visiting neighboring or adjacent folders on the same level before moving to the next folder level. This approach ensures that we will open one root folder and then visit all the folders in the root folder (Same level). Once we are done with the first level then will follow the same approach with each folder continuously until we reach our goal. In terms of sliding puzzles, BFS is like exploring potential moves level by level, guaranteeing the shortest path.
DFS Approach
Alternatively, we decide to explore the folder more quickly by going in a single direction like opening the root folder then having three folders in it then selecting any one folder then exploring it then selecting one folder from there as well, and continuing the same. Here we are diving deeply until we reach our goal or no data is found if no data is found then we backtrack and will check with another folder in the same manner. In a sliding puzzle context, DFS might dive deeply into a particular branch of moves before backtracking, which potentially leads to the solution faster, but at the cost of possibly taking longer to find the optimal path.
If you want to take in depth knowledge about the same follow my Youtube channel:
https://youtu.be/POM4mmLctyo?si=Hcbb-TQbXlrfAI9t
Sample INPUTS: Initial Grid: [[1, 2, 3], [0, 4, 6], [7, 5, 8]] Result Grid: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Program IN PHP:Sample Grids: Initial Grid: [[1, 2, 3], [0, 4, 6], [7, 5, 8]] Result Grid: [[1, 2, 3], [4, 5, 6], [7, 8, 9]] <?php class Puzzle{ protected $currRow,$currCol; protected $moveRow,$moveCol; protected $blankRow,$blankCol; public $move; public $matrixArr; public $visitedArr; /** *@description possibleMoves: Check possible moves U,D,L,R and then move it and return moves in array form *@param ARRAY $matrixArr *@return Array Moves */ public function possibleMoves(array $matrixArr){ //Getting current MATRIX Blank Position each time when we need to move the blank $this->move = []; $this->getBlankPos($matrixArr); //Moving blank Right (Current row and +1 in current col) $this->canMove($matrixArr, $this->blankRow, $this->blankCol+1); //Moving down $this->canMove($matrixArr, $this->blankRow-1, $this->blankCol); //Moving Up $this->canMove($matrixArr, $this->blankRow+1, $this->blankCol); //Moving Left (Current ROW AND -1 IN CURRENT COL) $this->canMove($matrixArr, $this->blankRow, $this->blankCol-1); return $this->move; } /** *@description moveElement: Moving blank [in array] on a specific position provided row,col and adding to an array *@param ARRAY $matrixArr *@param int $destRow [Destination Row] *@param int $destCol [Destination Col] */ public function moveElement($matrixArr, $destRow, $destCol){ $temp = $matrixArr[$destRow][$destCol];//Assigning $matrixArr[$destRow][$destCol] = $matrixArr[$this->blankRow][$this->blankCol]; $matrixArr[$this->blankRow][$this->blankCol] = $temp; $this->move[] = $matrixArr; } /** *@description canMove: Is our blank or zero movable to the given position *@param ARRAY $matrixArr *@param int $newRowPos [Destination Row] *@param int $newColPos [Destination Col] *@return boolean */ public function canMove($matrixArr, $newRowPos, $newColPos){ if($newRowPos< 0 || $newColPos< 0 || $newRowPos>2 || $newColPos > 2){ return false; }else{ $this->moveElement($matrixArr, $newRowPos, $newColPos); return true; } } /** *@description printMatrix: To print our matrix 2d array only *@param ARRAY $matrixArr *@return void */ public function printMatrix(array $matrixArr){ echo "\n"; for($i=0;$i<3;$i++){ for($j=0;$j<3;$j++){ echo $matrixArr[$i][$j]." "; } echo "\n"; } echo ""; } /** *@description printMatrix: To check where is our blank/zero positioned *@param ARRAY $matrixArr */ public function getBlankPos(array $matrixArr){ for($i=0;$i<3;$i++){ for($j=0;$j<3;$j++){ if($matrixArr[$i][$j] == 0){ $this->blankRow = $i; $this->blankCol = $j; break 2; } } } } /** *@description : Checks if resultant and initial array are same or not *@param ARRAY $initialArr *@param ARRAY $goalArr * @return boolean */ public function goalReached(array $initialArr, array $goalArr){ return $initialArr == $goalArr ? true : false; } /** *@description : Checks whether is there any new move already exists in visited array if yes then its duplicate move *@param ARRAY $initialArr *@param ARRAY $goalArr *@return Boolean */ public function checkDuplicateMove($move){ if(!empty($this->visitedArr) && in_array($move, $this->visitedArr)){ return true; }else{ $this->visitedArr[] = $move; return false; } } /** *@description : Counting the Depth *@param ARRAY $arr : Associative array for each tree level *@param ARRAY $initialArr *@return Int $depth */ public function getDepth($arr, $initialArr){ $depth = 0; $newArr = array_reverse($arr); $search; $found = false; for($i=0; $i<count($newArr); $i++){ foreach($newArr as $k=>$v){ if(!$found){ $searchKey = $k; $found = true; } foreach($v as $key=>$val){ if($searchKey == $val){ $searchKeyArr[] = $searchKey; $searchKey = $k; $depth++; } if($searchKey == json_encode($initialArr)){ $depth++; break 3; } } } } return $depth; } /** * @description: Print answer * @param Array: $arr * @param Boolean: @$isMaxStepReached */ public function printAnswer(array $arr, $isMaxStepReached){ echo "\n########## Results For Algo: ".$arr['algo']."################"; if(!$isMaxStepReached){ echo "\nGoal State: Reached!"; echo "\nSearched Total Depth: ".($arr['depth']); echo "\nSearched Total Iteration: ".$arr['steps']."\n"; echo 'Total Time taken to solve using '.$arr['algo'].': In ', $arr['time'], ' seconds'; }else{ echo "\nGoal State: Not Reached! [As Per H/W Configuration below are the max iteration and Depth Searched]"; echo "\nSearched total Iterations: ".$arr['steps']; echo "\nSearched Total Depth:".$arr['depth']; echo "\nTotal Time Taken in seconds:".$arr['time'],' seconds'; } } } /* @description: In order to call different BFS and DFS class we have created this class */ class SolvePuzzle{ /* *@description: In order to run the functionality of BFS or to check BFS result. *@param: array: $matrixArr *@param: array: $resultMatrix */ public function useBFS($matrixArr, $resultMatrix, $maxSteps){ $start = microtime(true); $obj = new Puzzle(); $queue = new SplQueue(); $queue->enqueue($matrixArr); $queue->rewind(); $stepCntr = 0; $arrQ = []; $maxStepReached = false; while($queue->count()>0){ $subctr = 0; $currentPos = new Puzzle(); //taking reference of last queue in temp reference of BFS SO OUR HEAD $obj is on top always $currentPos = $queue->dequeue(); if($obj->goalReached($currentPos, $resultMatrix)){ break ; } $obj->checkDuplicateMove($currentPos); //Making possible moves $moves = $obj->possibleMoves($currentPos); foreach($moves as $newMove){ if(!$obj->checkDuplicateMove($newMove)){ $queue->enqueue($newMove); $arrQ[json_encode($currentPos)][] = json_encode($newMove); } if($obj->goalReached($newMove, $resultMatrix)){ break 2; } } $queue->rewind(); $stepCntr++; //If Given Max Steps reached then break from loop if($maxSteps == $stepCntr){ $maxStepReached = true; break; } } $depth = $obj->getDepth($arrQ, $matrixArr); $end = microtime(true); $time = number_format(($end - $start), 9); $obj->printAnswer(['algo'=>'BFS', 'depth' => $depth, 'time'=>$time, 'steps'=>$stepCntr],$maxStepReached); } /* *@description: In order to run the functionality of DFS or to check DFS result. *@param: array: $matrixArr *@param: array: $resultMatrix */ public function useDFS($matrixArr, $resultMatrix, $maxSteps){ $start = microtime(true); $obj = new Puzzle(); $stack = new SplStack(); $stack->push($matrixArr); $arrQ = []; $stepCntr = 0; $isMaxStepReached = false; //Adding in the Visited Array as duplicate moves checks duplicate otherwise adds in visited array $obj->checkDuplicateMove($matrixArr); while($stack->count() > 0){ $currentPos = $stack->pop(); $moves = $obj->possibleMoves($currentPos); foreach($moves as $newMove){ if(!$obj->checkDuplicateMove($newMove)){ $stack->push($newMove); $arrQ[json_encode($currentPos)][] = json_encode($newMove); } if($obj->goalReached($newMove, $resultMatrix)){ break 2; } } $stepCntr++; if($maxSteps == $stepCntr){ $isMaxStepReached = true; break; } } $depth = $obj->getDepth($arrQ, $matrixArr); $end = microtime(true); $time = number_format(($end - $start), 9); $obj->printAnswer(['algo'=>'DFS', 'depth' => $depth, 'time'=>$time, 'steps'=>$stepCntr] ,$isMaxStepReached); } } $matrixArr = [ [1, 2, 3], [0, 4, 6], [7, 5, 8] ]; $resultMatrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 0] ]; $maxIterations = 5000; $puzzle = new Puzzle(); echo "Initial Matrix:"; $puzzle->printMatrix($matrixArr); echo "Result Matrix:"; $puzzle->printMatrix($resultMatrix); $puzzleSolve = new SolvePuzzle(); $puzzleSolve->useBFS($matrixArr, $resultMatrix, $maxIterations); $puzzleSolve->useDFS($matrixArr, $resultMatrix, $maxIterations); ?>
Python Script:import sysimport numpy as npimport csvimport osimport timeclass Node: def __init__(self, state, parent, action): self.state = state self.parent = parent self.action = actionclass QueueFrontier: def __init__(self): self.frontier = [] def add(self, node): self.frontier.append(node) def contains_state(self, state): return any((node.state[0] == state[0]).all() for node in self.frontier) def empty(self): return len(self.frontier) == 0 def remove(self): if self.empty(): raise Exception("Empty Frontier") else: node = self.frontier[0] self.frontier = self.frontier[1:] return nodeclass Puzzle: def __init__(self, start, startIndex, goal, goalIndex): self.start = [start, startIndex] self.goal = [goal, goalIndex] self.solution = None self.num_explored = 0 self.search_depth = 0 self.max_search_depth = 0 def neighbors(self, state): mat, (row, col) results = [] if row > 0: mat1 = np.copy(mat) mat1[row][col] = mat1[row - 1][col] mat1[row - 1][col] = 0 results.append(('up', [mat1, (row - 1, col)])) if col > 0: mat1 = np.copy(mat) mat1[row][col] = mat1[row][col - 1] mat1[row][col - 1] = 0 results.append(('left', [mat1, (row, col - 1)])) if row < 2: mat1 = np.copy(mat) mat1[row][col] = mat1[row + 1][col] mat1[row + 1][col] = 0 results.append(('down', [mat1, (row + 1, col)])) if col < 2: mat1 = np.copy(mat) mat1[row][col] = mat1[row][col + 1] mat1[row][col + 1] = 0 results.append(('right', [mat1, (row, col + 1)])) return results def print(self): solution = self.solution if self.solution is not None else None print("Start State:\n", self.start[0], "\n") print("Goal State:\n", self.goal[0], "\n") print("\nStates Explored: ", self.num_explored, "\n") print("Solution:\n ") for action, cell in zip(solution[0], solution[1]): print("action: ", action, "\n", cell[0], "\n") print("Goal Reached!!") def solve(self): start_time = time.time() visited = set() start = Node(state=self.start, parent=None, action=None) frontier = QueueFrontier() frontier.add(start) # self.explored = [] while True: if frontier.empty(): raise Exception("No solution") node = frontier.remove() self.num_explored += 1 if (node.state[0] == self.goal[0]).all(): actions = [] cells = [] while node.parent is not None: actions.append(node.action) cells.append(node.state) node = node.parent actions.reverse() cells.reverse() self.solution = (actions, cells) self.search_depth = len(actions) break set_of_tuples = tuple(tuple(row) for row in node.state[0]) set_of_tuplesgoal = tuple(tuple(row) for row in self.goal[0]) if set_of_tuples == set_of_tuplesgoal: break visited.add(set_of_tuples) for action, state in self.neighbors(node.state): set_of_tuplesstate = tuple(tuple(row) for row in state[0]) if set_of_tuplesstate not in visited: child = Node(state=state, parent=node, action=action) set_of_tupleschild = tuple(tuple(row) for row in child.state[0]) visited.add(set_of_tupleschild) frontier.add(child) # self.explored.append(child.state) self.max_search_depth = max(self.max_search_depth, len(frontier.frontier)) end_time = time.time() self.running_time = end_time - start_time # Creating the puzzle and solving it start = np.array([[3,2,1], [4,5,6], [8, 7, 0]]) goal = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 0]]) startIndex = (2, 2) goalIndex = (2, 2) p = Puzzle(start, startIndex, goal, goalIndex) p.solve() # Printing the additional parameters p.print() print("Start State:\n", start, "\n") print("Goal State:\n", goal, "\n") print("Path to Goal:", p.solution[0]) print("Cost of Path:", len(p.solution[0])) print("Running Time:", p.running_time, "seconds") print("Search Depth:", p.search_depth) print("Max Search Depth:", p.max_search_depth)
Like
Celebrate
Support
Love
Insightful
Funny
21
2 Comments
Yajush Pratap Singh
Software engineer at Sopra Steria
11mo
- Report this comment
code is not working
1Reaction
See more comments
To view or add a comment, sign in
More articles by this author
No more previous content
- Online Attendance System (Without Ethernet) May 28, 2020
No more next content
Sign in
Stay updated on your professional world
Sign in
By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.
New to LinkedIn? Join now
Explore topics
- Sales
- Marketing
- IT Services
- Business Administration
- HR Management
- Engineering
- Soft Skills
- See All