How to solve 8 Puzzle problems using BFS and DFS and compare both in order to get optimal results? (2024)

INITIAL STATE GOAL STATE 1 2 3 1 2 3 0 4 6 => 4 5 6 7 5 8 7 8 0 

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)