output_description: Print the fewest steps in a line.
input_description: The $3 \times 3$ integers denoting the pieces or space are given.
attempt: # -*- coding: utf-8 -*-
  
  import sys
  from collections import deque
  
  
  def input():
      return sys.stdin.readline().strip()
  
  
  def list2d(a, b, c):
      return [[c] * b for i in range(a)]
  
  
  def list3d(a, b, c, d):
      return [[[d] * c for j in range(b)] for i in range(a)]
  
  
  def ceil(x, y=1):
      return int(-(-x // y))
  
  
  def INT():
      return int(input())
  
  
  def MAP():
      return map(int, input().split())
  
  
  def LIST():
      return list(map(int, input().split()))
  
  
  def Yes():
      print("Yes")
  
  
  def No():
      print("No")
  
  
  def YES():
      print("YES")
  
  
  def NO():
      print("NO")
  
  
  sys.setrecursionlimit(10**9)
  INF = float("inf")
  MOD = 10**9 + 7
  
  N = 3
  # グリッドを最初から文字列として1次元で保持する
  grid = "*" * (N + 2)
  for i in range(N):
      grid += "*" + input().replace(" ", "") + "*"
  grid += "*" * (N + 2)
  start = grid.find("0")
  
  # 完成形の盤面
  goal = "******123**456**780******"
  que = deque()
  que.append((grid, 0, start))
  # その盤面に至る移動コスト
  memo = {}
  while len(que):
      grid, cost, cur = que.popleft()
      if grid in memo:
          continue
      memo[grid] = cost
      grid = list(grid)
      # 4方向見る
      for direction in (-1, 1, -(N + 2), N + 2):
          nxt = cur + direction
          if grid[nxt] != "*":
              grid[cur], grid[nxt] = grid[nxt], grid[cur]
              que.append(("".join(grid), cost + 1, nxt))
              grid[cur], grid[nxt] = grid[nxt], grid[cur]
  
  print(memo[goal])
  
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"}]