title: Path finding: A star not same length from A to B than from B to A
body: <p>I am implementing the A star algorithm with the Manhattan distance for the 8 puzzle. [ The solution is in spiral form]</p>
  
  <pre><code>1 2 3
  8 0 4
  7 6 5
  </code></pre>
  
  <p>In some case, going from A to B will not take the same number of steps as going from B to A.</p>
  
  <p>I think this is because it does not pick the same state on the open list, when they have the same cost, thus, not expanding the same nodes.</p>
  
  <p>From</p>
  
  <pre><code> 7 6 4 
   1 0 8 
   2 3 5
  
  
  
   (A -&gt; B)
  
   7 6 4 
   1 8 0 
   2 3 5 
  
   (B -&gt; A)
  
   7 6 4 
   1 3 8 
   2 0 5
  </code></pre>
  
  <p>Which both have the same value using Manhattan distance.
  Should I explore all path with the same value?
  Or should I change the heuristic to have some kind of tie-breaker?</p>
  
  <p>Here is the relevant part of the code</p>
  
  <pre><code> def solve(self):
      cost = 0
      priority = 0
      self.parents[str(self.start)] = (None, 0, 0)
      open = p.pr() #priority queue
      open.add(0, self.start, cost)
      while open:
         current = open.get()
         if current == self.goal:
          return self.print_solution(current)
         parent = self.parents[str(current)]
         cost = self.parents[str(current)][2] + 1
         for new_state in self.get_next_states(current):
           if str(new_state[0]) not in self.parents or cost &lt; self.parents[str(new_state[0])][2]:
             priority = self.f(new_state) + cost
             open.add(priority, new_state[0], cost)
             self.parents[str(new_state[0])] = (current, priority, cost)
  </code></pre>