1. **Problem Statement:** Traverse the given 6x6 maze from the start cell S at (0,2) to the goal cell G at (5,5) using Depth-First Search (DFS). Walls are blocked cells and cannot be traversed. Movement is allowed only in four directions: East, West, South, North, in that order. 2. **DFS Algorithm and Rules:** - DFS explores as far as possible along each branch before backtracking. - The order of movement directions is East, West, South, North. - Already visited cells are not revisited. - Each move costs 1 unit. 3. **Maze Setup:** - Start: S = (0,2) - Goal: G = (5,5) - Walls at: (1,1), (2,1), (3,1), (5,1), (3,3), (4,3), (5,3), (4,4), (1,5) 4. **Step-by-step DFS traversal:** - Start at (0,2) - From (0,2), try East: (0,3) open → move to (0,3) - From (0,3), East: (0,4) open → move to (0,4) - From (0,4), East: (0,5) open → move to (0,5) - From (0,5), East: (0,6) out of bounds → backtrack - West: (0,4) visited → backtrack - South: (1,5) wall → backtrack - North: (-1,5) out of bounds → backtrack - Back to (0,4), West: (0,3) visited → backtrack - South: (1,4) open → move to (1,4) - From (1,4), East: (1,5) wall → backtrack - West: (1,3) wall → backtrack - South: (2,4) open → move to (2,4) - From (2,4), East: (2,5) open → move to (2,5) - From (2,5), East: (2,6) out of bounds → backtrack - West: (2,4) visited → backtrack - South: (3,5) open → move to (3,5) - From (3,5), East: (3,6) out of bounds → backtrack - West: (3,4) wall → backtrack - South: (4,5) open → move to (4,5) - From (4,5), East: (4,6) out of bounds → backtrack - West: (4,4) wall → backtrack - South: (5,5) goal → move to (5,5) 5. **Order of visited squares:** (0,2) → (0,3) → (0,4) → (0,5) → (1,4) → (2,4) → (2,5) → (3,5) → (4,5) → (5,5) 6. **Path cost:** Number of moves = number of steps from start to goal = 9 moves 7. **Summary:** The DFS path from S to G is: $$ (0,2) \to (0,3) \to (0,4) \to (0,5) \to (1,4) \to (2,4) \to (2,5) \to (3,5) \to (4,5) \to (5,5) $$ The total path cost is: $$ 9 \text{ units} $$