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 sys
  import queue
  
  N = 3
  f = "".join(sys.stdin.readline().split())
  f += "".join(sys.stdin.readline().split())
  f += "".join(sys.stdin.readline().split())
  
  dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]
  
  Q = queue.Queue()
  V = dict()
  
  Q.put([f, f.index("0"), 0])
  V[f] = True
  
  while not Q.empty():
      u = Q.get()
      if u[0] == "123456780":
          break
      sx, sy = u[1] // N, u[1] % N
      for dx, dy in dd:
          tx, ty = sx + dx, sy + dy
          if tx < 0 or ty < 0 or tx >= N or ty >= N:
              continue
          v = u[:]
          n1, n2 = u[1], tx * N + ty
          v[1] = n2
          if n1 > n2:
              n1, n2 = n2, n1
          v[0] = v[0][0:n1] + v[0][n2] + v[0][n1 + 1 : n2] + v[0][n1] + v[0][n2 + 1 :]
          if not V.get(v[0], False):
              V[v[0]] = True
              v[2] += 1  # dir[r]
              Q.put(v)
  
  print(u[2])
  
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"}]