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 heapq
  from collections import namedtuple
  
  
  def get_offset(x, y):
      return 16 * y + 4 * x
  
  
  def get_candidate(pid):
      def check(pid, move):
          if abs(move) == 1:
              return pid // 4 == (pid + move) // 4
          else:
              return 0 <= pid + move < 16
  
      return tuple(pid + move for move in MOVE_CANDIDATE if check(pid, move))
  
  
  def get_swap_values(orig):
      return {
          dest: (1 << OFFSET_MASTER[orig]) - (1 << OFFSET_MASTER[dest])
          for dest in SWAP_CANDIDATE[orig]
      }
  
  
  MOVE_CANDIDATE = (-4, -1, 1, 4)
  SWAP_CANDIDATE = tuple(get_candidate(pid) for pid in range(16))
  OFFSET_MASTER = tuple(get_offset(x, y) for y in range(4) for x in range(4))
  SWAP_VALUE_MASTER = tuple(get_swap_values(pid) for pid in range(16))
  HEURISTICS = tuple(
      tuple(abs(dest // 4 - orig // 4) + abs(dest % 4 - orig % 4) for dest in range(16))
      for orig in range(16)
  )
  
  
  def swap(board, orig, dest):
      dest_val = (board >> OFFSET_MASTER[dest]) & 0b1111
      return board + dest_val * SWAP_VALUE_MASTER[orig][dest]
  
  
  def get_sum_heuristics(orig_board, is_reverse):
      global dest_board_dicts
      orig_board_dict = {i: orig_board >> (4 * i) & 0b1111 for i in range(16)}
      dest_board_dict = dest_board_dicts[is_reverse]
  
      return sum(
          HEURISTICS[pid][dest_board_dict[val]] for pid, val in orig_board_dict.items()
      )
  
  
  def put_next_puzzle(is_reverse):
      global puzzles, cache
      (heur, puzzle) = heapq.heappop(puzzles[is_reverse])
      board, id0, count, prev = puzzle.board, puzzle.id0, puzzle.count, puzzle.prev
      for new_id0 in SWAP_CANDIDATE[id0]:
          if new_id0 == prev:
              continue
  
          new_board = swap(board, id0, new_id0)
  
          if new_board in cache[not is_reverse]:
              return cache[not is_reverse][new_board].count + count + 1
  
          new_heur = count + 1 + get_sum_heuristics(new_board, is_reverse)
          if new_board in cache[is_reverse]:
              closed_puzzle = cache[is_reverse][new_board]
              if closed_puzzle.heur <= new_heur:
                  continue
  
          new_puzzle = Puzzle(
              board=new_board,
              count=count + 1,
              id0=new_id0,
              prev=id0,
              trace=puzzle.trace * 16 + new_id0,
              heur=new_heur,
          )
          heapq.heappush(puzzles[is_reverse], (new_heur, new_puzzle))
          cache[is_reverse][new_board] = new_puzzle
      return -1
  
  
  CORRECT = 0x0FEDCBA987654321
  Puzzle = namedtuple("Puzzle", "board count id0 prev trace heur")
  puzzles = ([], [])
  cache = ({}, {})
  board = 0
  id0 = -1
  
  for j in range(4):
      for i, v in enumerate(map(int, input().strip().split())):
          board += v << get_offset(i, j)
          if v == 0:
              id0 = 4 * j + i
  
  dest_board_dicts = (
      {CORRECT >> (4 * i) & 0b1111: i for i in range(16)},
      {board >> (4 * i) & 0b1111: i for i in range(16)},
  )
  s_heur = get_sum_heuristics(board, False)
  g_heur = get_sum_heuristics(CORRECT, True)
  s_puzzle = Puzzle(
      board=board, count=0, id0=id0, prev=-1, trace=0, heur=get_sum_heuristics(board, 0)
  )
  g_puzzle = Puzzle(
      board=CORRECT,
      count=0,
      id0=15,
      prev=-1,
      trace=0,
      heur=get_sum_heuristics(CORRECT, 1),
  )
  heapq.heappush(puzzles[0], (s_heur, s_puzzle))
  heapq.heappush(puzzles[1], (g_heur, g_puzzle))
  cache[0][board] = s_puzzle
  cache[1][CORRECT] = g_puzzle
  result = None
  is_reverse = False
  
  while True:
      result = put_next_puzzle(is_reverse)
      if result > -1:
          break
      is_reverse = not is_reverse
  
  print(result)
  
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"}]