output_description: Print the fewest steps in a line.
input_description: The $3 \times 3$ integers denoting the pieces or space are given.
attempt: from collections import deque
  
  MOVE = {"U": (0, -1), "D": (0, 1), "L": (-1, 0), "R": (1, 0)}
  
  
  def next(numbers):
      for d in "UDLR":
          z = numbers.index(0)
          tx, ty = z % 3 + MOVE[d][0], z
          if 0 <= tx < 3 and 0 <= ty < 3:
              t = ty * 3 + tx
              result = list(numbers)
              result[z], result[t] = numbers[t], 0
              yield d, tuple(result)
  
  
  def bfs(puzzle):
      queue = deque([(puzzle, "")])
      seen = set()
      while queue:
          numbers, route = queue.popleft()
          seen.add(numbers)
          if numbers == (1, 2, 3, 4, 5, 6, 7, 8, 0):
              return route
          for direction, new_numbers in next(numbers):
              if new_numbers not in seen:
                  queue.append((new_numbers, route + direction))
      return route
  
  
  puzzle = ()
  for i in range(3):
      a, b, c = map(int, input().split())
      puzzle += (a, b, c)
  
  print(len(bfs(puzzle)))
  
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"}]