output_description: Print the fewest steps in a line.
input_description: The $3 \times 3$ integers denoting the pieces or space are given.
attempt: N = 3
  # f = [input().split() for _ in range(3)]
  f = input().split()
  f += input().split()
  f += input().split()
  dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]
  
  Q = [[f, f.index("0"), 0]]
  # T = {f: True}
  T = set(f)
  
  while len(Q) > 0:
      board = Q.pop(0)
      if board[0] == ["1", "2", "3", "4", "5", "6", "7", "8", "0"]:
          break
      x, y = int(board[1] / N), board[1] % N
      for dx, dy in dd:
          tx, ty = x + dx, y + dy
          if tx < 0 or ty < 0 or tx >= N or ty >= N:
              continue
          new = board[:]
  
          n1, n2 = board[1], tx * N + ty
          new[1] = n2
          # swap
          if n1 > n2:
              n1, n2 = n2, n1
          # swaped string
          new[0] = (
              new[0][0:n1]
              + list(new[0][n2])
              + new[0][n1 + 1 : n2]
              + list(new[0][n1])
              + new[0][n2 + 1 :]
          )
          hashstr = "".join(new[0])
          if hashstr not in T:
              # T[new[0]] = True
              T.add(hashstr)
              new[2] += 1
              Q.append(new)
  
  print(board[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"}]