In one sentence explanation for each class, and each method in each class. Specify the class attributes. Go through the classes in this order:

1.  
2. TileState
3.  
4. TileProblem
5.  
6. GraphTraverser
7.   
8. 
   
9. class TileState:
      #define a new Tile state given the locations of the tiles
      def __init__(self, s, i,j):
          self.state = s
          self.x = i
          self.y = j
          self.set_state_name()
          
      def set_state_with_name(self, s_name):
          self.state=[]
          #print("inside set state with name. State = \n****\n", s_name)
          #set state
          lines = s_name.split('\n')
          lines.pop() #remove last line as it is empty.
          for line in lines:
              lst=[]
              ns = line.split(',')
              for i in range(3):
                  lst.append(int(ns[i]))
              self.state.append(lst)
          #set location of empty tile
          for i in range(3):
              for j in range(3):
                  if self.state[i][j]==-1:
                      self.x=i
                      self.y=j
                      break
          
      #the state name shows the tile locations as a string
      def set_state_name(self):
          if self.state is None:
              self.state_name='None'
              #print('Can\'t set state name. State is None!')
              return
          name = ''
          s = self.state
          for i in range(0,len(s)):
              for j in range(0,len(s)):
                  name = name + str(s[i][j]) + ','
              name = name+'\n'
          self.state_name = name
      

#=============================================
#=============================================
#=============================================

#tile problem class to hold all information about the tile problem
class TileProblem:
   
   #istate is an object of tyle TileState
   def __init__(self, istate):
       self.initial_state = istate
       self.n_tiles = 3
       #ideal locations of tiles:
       self.goal_loc = []
       self.goal_loc.append( (0,0) ) #empty tile at 0,0
       #1 => 0,1
       self.goal_loc.append((0,1))
       # 2 => 0,2
       self.goal_loc.append((0,2))
       # 3 => 1,0
       self.goal_loc.append((1,0))
       # 4 => 1,1
       self.goal_loc.append((1,1))
       # 5 => 1,2
       self.goal_loc.append((1,2))
       # 6 => 2,0
       self.goal_loc.append((2,0))
       # 7 => 2,1
       self.goal_loc.append((2,1))
       # 8 => 2,2
       self.goal_loc.append((2,2))
       
   #tstate is an object of type TileState
   def expand_state(self, tstate):
       x = tstate.x
       y = tstate.y
       nbr_states = []
       
       #move right
       if x>0:
           rt_mv_s = copy.deepcopy(tstate.state)
           rt_mv_s[x][y] = rt_mv_s[x-1][y] # move tile right
           rt_mv_s[x-1][y] = -1 # set new empty tile
           ts = TileState(rt_mv_s, x-1, y) #create new tilestate
           nbr_states.append(ts) #append new tilestate to neighbors
       #move left
       if x           lt_mv_s = copy.deepcopy(tstate.state)
           lt_mv_s[x][y] = lt_mv_s[x+1][y] # move tile left
           lt_mv_s[x+1][y] = -1 # set new empty tile
           ts = TileState(lt_mv_s, x+1, y) #create new tilestate
           nbr_states.append(ts) #append new tilestate to neighbors
       #move down
       if y>0:
           dn_mv_s = copy.deepcopy(tstate.state)
           dn_mv_s[x][y] = dn_mv_s[x][y-1] # move tile down
           dn_mv_s[x][y-1] = -1 # set new empty tile
           ts = TileState(dn_mv_s, x, y-1) #create new tilestate
           nbr_states.append(ts) #append new tilestate to neighbors
       #move up
       if y           up_mv_s = copy.deepcopy(tstate.state)
           up_mv_s[x][y] = up_mv_s[x][y+1] # move tile up
           up_mv_s[x][y+1] = -1 # set new empty tile
           ts = TileState(up_mv_s, x, y+1) #create new tilestate
           nbr_states.append(ts) #append new tilestate to neighbors
       
       return nbr_states

   #get the cost of a state by adding distances of tiles to their goal states
   def get_state_cost(self,tstate):
       locs = tstate.state
       sum_dist = 0
       for i in range(0,self.n_tiles):
           for j in range(0,self.n_tiles):
               
               num = locs[i][j]
               if num == -1:
                   continue
               (i_goal, j_goal) = self.goal_loc[num]
               sum_dist += abs(i_goal-i) + abs(j_goal-j)
       return sum_dist
   
   def is_goal_state(self, tstate):
       sum_dist = self.get_state_cost(tstate)
       if sum_dist == 0:
           return True
       else:
           return False

 

class GraphTraverser:
   
   def __init__(self, g):
       self.graph = g
       self.tree = Tree()

   #===========================================
   
   #===========================================
         
   def a_star_traversal(self, tile_problem):
       #extract initial state
       initial_state = tile_problem.initial_state
       
       #check if initial state is the goal state
       if tile_problem.is_goal_state(initial_state):
           print("Initial state is goal state!")
           return
       
       #set data structures
       reached_states_cost_hn = {}
       reached_states_cost_gn = {}
       reached_states_cost_hn[initial_state.state_name] = tile_problem.get_state_cost(initial_state)
       reached_states_cost_gn[initial_state.state_name] = 0

       states_to_expand = {initial_state.state_name:1}
       
 
       self.tree = Tree()
       rootNode = TreeNode(initial_state.state_name, None)
       self.tree.set_root(rootNode)
       
       #expand initial state and append all states into the data structures
               
       #while loop: keep expanding states until a goal state is reached
       while len(states_to_expand)>0:
           #compute all state costs
           cost_fn={}
           for c_state in states_to_expand:
               cost_fn[c_state] = reached_states_cost_hn[c_state] + reached_states_cost_gn[c_state]
           
           #find min-cost state
           min_cost_state_name = min(cost_fn, key=cost_fn.get)
           
           #pop the min cost state from the states_to_expand list:
           states_to_expand.pop(min_cost_state_name)
           
           #a state using the state name:
           exp_state = TileState(None, -1,-1)
           exp_state.set_state_with_name(min_cost_state_name)
           #print("state created for min-cost state:\n")
           #print(exp_state.state)
           #print(exp_state.x, exp_state.y)
           
           #check if goal state then return solution
           if tile_problem.is_goal_state(exp_state):
               print("Solution Found!: ", min_cost_state_name)
               self.tree.print_path(TreeNode(min_cost_state_name,''))
               break
           
           #expand all its neighboring states
           expanded_states = tile_problem.expand_state(exp_state)

           #find neighbors' costs and add to expansion & reach lists & the traversal tree
           for state in expanded_states:
               #check if state has been previously reached, in which case, don't re-add as this will lead to infinite loops
               if state.state_name not in reached_states_cost_hn:
                   reached_states_cost_hn[state.state_name] = tile_problem.get_state_cost(state)
                   reached_states_cost_gn[state.state_name] = reached_states_cost_gn[min_cost_state_name] + 1 # these states are 1 step away from the state being expanded now
                   states_to_expand[state.state_name]=1
                   #add node to traversal tree. all edge weights = 1 since each expanded state is one move away from its parent state
                   n = TreeNode(state.state_name, min_cost_state_name)
                   self.tree.add_child_node( n, min_cost_state_name, 1)