output_description: Print the fewest steps in a line.
input_description: The $3 \times 3$ integers denoting the pieces or space are given.
attempt: import heapq
  
  
  def check_goal(p):
      return p == [1, 2, 3, 4, 5, 6, 7, 8, 0]
  
  
  def up(p):
      q = p.copy()
      zero = p.index(0)
      q[zero] = q[zero - 3]
      q[zero - 3] = 0
      return q
  
  
  def low(p):
      q = p.copy()
      zero = p.index(0)
      q[zero] = q[zero + 3]
      q[zero + 3] = 0
      return q
  
  
  def right(p):
      q = p.copy()
      zero = p.index(0)
      q[zero] = q[zero + 1]
      q[zero + 1] = 0
      return q
  
  
  def left(p):
      q = p.copy()
      zero = p.index(0)
      q[zero] = q[zero - 1]
      q[zero - 1] = 0
      return q
  
  
  def cost(p, n_mov):
      c = n_mov
      for i in range(9):
          if p[i] != (i + 1) % 9:
              c += 1
      return c
  
  
  def solve(p):
      ans = 0
      zero = p.index(0)
      will = list()
      done = [p]
      while not check_goal(p):
          ans += 1
          if zero >= 3 and up(p) not in done:
              done.append(up(p))
              heapq.heappush(will, (up(p), ans))
          if zero <= 5 and low(p) not in done:
              done.append(low(p))
              heapq.heappush(will, (low(p), ans))
          if zero % 3 <= 1 and right(p) not in done:
              done.append(right(p))
              heapq.heappush(will, (right(p), ans))
          if zero % 3 >= 1 and left(p) not in done:
              done.append(left(p))
              heapq.heappush(will, (left(p), ans))
          p, ans = heapq.heappop(will)
          zero = p.index(0)
      return ans
  
  
  p = list(map(int, input().split()))
  p.extend(list(map(int, input().split())))
  p.extend(list(map(int, input().split())))
  print(solve(p))
  
problem_description: 8 Puzzle
  
  The goal of the 8 puzzle problem is to complete pieces on $3 \times 3$ cells
  where one of the cells is empty space.
  
  In this problem, the space is represented by 0 and pieces are represented by
  integers from 1 to 8 as shown below.
  
      
      
      1 3 0
      4 2 5
      7 8 6
      
  
  You can move a piece toward the empty space at one step. Your goal is to make
  the pieces the following configuration in the shortest move (fewest steps).
  
      
      
      1 2 3
      4 5 6
      7 8 0
      
  
  Write a program which reads an initial state of the puzzle and prints the
  fewest steps to solve the puzzle.
samples: [{"input": "3 0\n    4 2 5\n    7 8 6", "output": "4"}]