output_description: Print the fewest steps in a line.
input_description: The $4 \times 4$ integers denoting the pieces or space are given.
attempt: import copy
  
  
  def hashnum(state):
      num = 0
      for i in range(3):
          for j in range(3):
              num *= 10
              num += state[i][j]
      return num
  
  
  answer = 123456780
  ini_state = []
  for i in range(3):
      temp = [int(n) for n in input().split(" ")]
      if 0 in temp:
          zero_x, zero_y = temp.index(0), i
      ini_state.append(temp)
  end_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
  queue = [[ini_state, zero_x, zero_y, 0], [end_state, 2, 2, 1]]
  dx = [1, 0, -1, 0]
  dy = [0, 1, 0, -1]
  visited = {}
  visited[hashnum(ini_state)] = [0, 0]
  visited[answer] = [0, 1]
  trial = 0
  while answer not in visited:
      new_queue = []
      trial += 1
      for q in queue:
          state, zero_x, zero_y, direction = q
          for i in range(len(dx)):
              new_state = copy.deepcopy(state)
              new_x = zero_x + dx[i]
              new_y = zero_y + dy[i]
              if 0 <= new_x < 3 and 0 <= new_y < 3:
                  new_state[new_y][new_x], new_state[zero_y][zero_x] = (
                      new_state[zero_y][zero_x],
                      new_state[new_y][new_x],
                  )
                  perm = hashnum(new_state)
                  if perm in visited and direction != visited[perm][1]:
                      print(trial + visited[perm][0])
                      exit()
                  if perm not in visited:
                      visited[perm] = [trial, direction]
                      new_queue.append([new_state, new_x, new_y, direction])
      queue = new_queue
  
problem_description: 15 Puzzle
  
  The goal of the 15 puzzle problem is to complete pieces on $4 \times 4$ 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 15 as shown below.
  
      
      
      1 2 3 4
      6 7 8 0
      5 10 11 12
      9 13 14 15
      
  
  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
      9 10 11 12
      13 14 15 0
      
  
  Write a program which reads an initial state of the puzzle and prints the
  fewest steps to solve the puzzle.
samples: [{"input": "2 3 4\n    6 7 8 0\n    5 10 11 12\n    9 13 14 15", "output": "8"}]