I'm trying to implement Depth Firs Search. Right now my program correctly finds the goal, but it seems to be going about it in the wrong way. The first image is my code and the second is results. What am I not handling correctly? According to the grader, I get the proper neighbor nodes, but my algorithm doesn't take the path the grader wants me to take.

#begin loop while not stack_for_pac.isEmpty(): #This is our open. It has two parts. Current x,y and the direction #Note: .pop() returns a tuple of 3 tiems, but only assigning 2 items works. current_Spot, direction = stack_for_pac.pop() #get Successors will give us useful information, but we only need the first two #elements of the tuples it returns. for i in problem.getSuccessors (current_Spot): #our new x, y next_Spot = i[0] #our new dirciton to take next_Direction = i[1] #if our next spot is not already in the closed list if next_Spot not in closed: #and if the next spot is our goal if problem.isGoalState (next_Spot): #pacman wins. return the starting direciton and a list of next directions if any return direction + [next_Direction] else: #else Pacman did not win, push new values and keep track of where Pacman is going stack_for_pac.push((next_Spot, direction + [next_Direction])) #update closed list closed.append(next_Spot) test_cases\ql\graph_manypaths.test graph: El Bi / V / V *A --> C --> D --> F --> [G] V 1 B2 V / E2 *** *** A is the start state, G is the goal. Arrows mark possible state transitions. This graph has multiple paths to the goal, where nodes with the same state are added to the fringe multiple times before they are expanded. student solution: ['1:A->C', 'O:C->D', '1:D->F', 'O:F->G'] student expanded states: ['A', 'B2', 'C', 'D', '2', 'F'] correct solution: ['2:A->B2', 'O:B2->C', 'O:C->D', '2:D->E2', 'O:E2->F', 'O:F->G'] correct expanded_states: ['A', '2', 'C', 'D', '2', 'F'] correct rev_solution: ['0:A->Bl', 'O:B1->C', '0:C->D', '0: D->El', '0:El->F', '0:F->G'] correct rev_expanded_states: ['A', 'l', 'C', 'D', 'El', 'F'] *** PASS: test_cases\ql\pacman_1.test pacman layout: mediumMaze solution length: 130 nodes expanded: 144 *** Tests failed