final the find-path method using DFS (recursive way)

import traceback, turtle

#Takes as input a Square object node in a graph of Square nodes. # This will always be the Square node representing (0,0), the start position #Performs DFS until the goal Square is found (the Square with val == 2). #Returns a list containing each Square node in the path from the start # (0,0) to the goal node, inclusive, in order from start to goal. def find_path(start_node): start_node.set_color("gray") start_node.prev = None #TODO: Finish the DFS and return the path from start_node to the goal return [start_node]

# DO NOT EDIT BELOW THIS LINE

#Square class #A single square on the grid, which is a single node in the graph. #Has several instance variables: # self.t: The turtle object used to draw this square # self.x: The integer x coordinate of this square # self.y: The integer y coordinate of this square # self.val: An integer, which is 0 if this square is blocked, 1 # if it's a normal, passable square, and 2 if it's the goal. # self.adj: A list representing all non-blocked squares adjacent # to this one. (This is the node's adjacency list) # self.__color: A private string representing the color of the square # Must be accessed using set_color and get_color because it's private # The color of the square is purple if it's a blocked square. # Otherwise, it starts as white, and then progresses to grey and then # black according to the DFS algorithm. # self.prev: A Square object pointing to the node from which this node # was discovered from within DFS: the pi variable in the textbook class Square: def __init__(self,x,y,val,t): self.t = t self.x = x self.y = y self.val = val self.adj = [] if self.val: self.__color = "white" else: self.__color = "purple" self.prev = None #Getters and setters for color variable. You MUST use these rather # than trying to change color directly: it causes the squares to # actually update color within the graphics window. def set_color(self,color):

if color != self.__color: self.__color = color self.draw() def get_color(self): return self.__color

#Draws the square def draw(self): t = self.t t.hideturtle() t.speed(0) t.pencolor("blue") if self.__color == "purple": t.pencolor("purple") if self.val != 2: t.fillcolor(self.__color) else: t.fillcolor("cyan") t.penup() t.setpos(self.x-.5,self.y-.5) t.pendown() t.begin_fill() for i in range(4): t.forward(1) t.left(90) t.end_fill() #String representation of a Square object: (x,y) def __repr__(self): return "("+str(self.x)+","+str(self.y)+")" #Check equality between two Square objects. def __eq__(self,other): return type(self) == type(other) and \ self.x == other.x and self.y == other.y