15-퍼즐은 $4 \times 4$ 크기의 판 위에 $1$부터 $15$까지의 숫자가 적힌 타일과 하나의 빈칸(0)이 있고, 빈칸과 인접한 타일을 밀어 움직여 타일들을 정렬하는 퍼즐입니다.
목표 상태는 다음과 같이 순서대로 정렬되는 것입니다:
1 2 3 4 / 5 6 7 8 / 9 10 11 12 / 13 14 15 0

초기 배치 상태가 주어질 때, 목표 상태를 만드는 데 필요한 최소 타일 이동 횟수를 구하십시오.
탐색 도중 시간 및 메모리를 절약하기 위해, 빈칸 이동에 의한 타일의 Inversion Count를 이용해 풀이 가능 여부(Solvability)를 조기에 판별하고, IDA* (Iterative Deepening A*) 알고리즘을 사용해 휴리스틱 가치를 계산하여 해결하십시오.

[제약 조건]
• 입력은 $4 \times 4$ 격자이며, 0은 빈칸을 나타냅니다.
• 숫자 1~15가 중복 없이 주어집니다.
• 풀이 불가능한 경우 -1을 출력합니다.

$4$개의 줄에 걸쳐 각 줄에 $4$개의 정수가 공백으로 구분되어 주어집니다. (0은 빈칸을 나타내며, 1부터 15까지의 숫자가 중복 없이 주어집니다)

목표 상태를 만드는 데 필요한 최소 이동 횟수를 출력합니다. 만약 목표 상태를 만드는 것이 원천적으로 불가능한 배치인 경우에는 -1을 출력합니다.

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

0