output_description: Print the fewest steps in a line.
input_description: The $3 \times 3$ integers denoting the pieces or space are given.
attempt: goal = ((1, 2, 3), (4, 5, 6), (7, 8, 0))
  
  parents = {}
  total = {}
  flag = True
  
  initial = []
  position = []
  for i in range(3):
      a, b, c = map(int, input().split())
      if a == 0:
          position.extend([i, 0])
      elif b == 0:
          position.extend([i, 1])
      elif c == 0:
          position.extend([i, 2])
      initial.append((a, b, c))
  
  parents[tuple(initial)] = position
  total[tuple(initial)] = 1
  
  count = 0
  
  if tuple(initial) == goal:
      flag = False
  
  while flag:
      count += 1
      children = {}
      for par_key in parents.keys():
          position = parents[par_key]
  
          if position[0] < 2:
              child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
              child[position[0]][position[1]] = child[position[0] + 1][position[1]]
              child[position[0] + 1][position[1]] = 0
              child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
              if child_tuple == goal:
                  flag = False
                  break
              elif child_tuple not in total:
                  children[child_tuple] = [position[0] + 1, position[1]]
                  total[child_tuple] = 1
  
          if position[0] > 0:
              child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
              child[position[0]][position[1]] = child[position[0] - 1][position[1]]
              child[position[0] - 1][position[1]] = 0
              child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
              if child_tuple == goal:
                  flag = False
                  break
              elif child_tuple not in total:
                  children[child_tuple] = [position[0] - 1, position[1]]
                  total[child_tuple] = 1
  
          if position[1] < 2:
              child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
              child[position[0]][position[1]] = child[position[0]][position[1] + 1]
              child[position[0]][position[1] + 1] = 0
              child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
              if child_tuple == goal:
                  flag = False
                  break
              elif child_tuple not in total:
                  children[child_tuple] = [position[0], position[1] + 1]
                  total[child_tuple] = 1
  
          if position[1] > 0:
              child = [list(par_key[0]), list(par_key[1]), list(par_key[2])]
              child[position[0]][position[1]] = child[position[0]][position[1] - 1]
              child[position[0]][position[1] - 1] = 0
              child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]))
              if child_tuple == goal:
                  flag = False
                  break
              elif child_tuple not in total:
                  children[child_tuple] = [position[0], position[1] - 1]
                  total[child_tuple] = 1
  
      parents = children
  
  print(count)
  
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"}]