Find minimum moves to solve the 15-puzzle
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
## Problem
Given a 4×4 sliding puzzle (the classic **15-puzzle**), compute the **minimum number of moves** required to reach the solved state, or return `-1` if it is impossible.
- The board contains numbers `1..15` and a blank represented by `0`.
- A move consists of swapping `0` with one of its 4-directional neighbors (up/down/left/right).
### Input
A 4×4 integer matrix `board`.
### Output
An integer `minMoves`:
- the minimum number of moves to reach the target state, or
- `-1` if the target state is unreachable.
### Target state
```
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
```
### Constraints/Notes
- You must handle unsolvable configurations.
- Aim for an approach that can finish in reasonable time for typical interview test cases (e.g., using an informed search such as A* rather than naive BFS over the full state space).
Quick Answer: This question evaluates understanding of state-space search, heuristic reasoning, and solvability analysis for combinatorial sliding puzzles, testing algorithm design and optimization within the Coding & Algorithms domain at a practical application level with required conceptual understanding of search-space properties.