Manhattan Heuristic

def cornersHeuristic(state, problem):
  """
  A heuristic for the CornersProblem that you defined.

    state:   The current search state (a data structure you chose in your search problem)
    problem: The CornersProblem instance for this layout.

  This function should always return a number that is a lower bound
  on the shortest path from the state to a goal of the problem; i.e.
  it should be admissible.  (You need not worry about consistency for
  this heuristic to receive full credit.)
  """
  corners = problem.corners # These are the corner coordinates
  walls = problem.walls # These are the walls of the maze, as a Grid (game.py)

#Manhattan heuristic:
  best = 999999
  for corner in corners:
    #Find manhattan value
    xy1 = state.getLoc()
    xy2 = corner
    value = abs(xy1[0] - xy2[0]) + abs(xy1[1] - xy2[1])
    if value < best:
      best = value
  #Return smallest manhattan value
  return best