Microsoft Interview Problem #1 — 8-Puzzle Minimum Moves

Description

The 8 Puzzle is a sliding block game played on a 3×3 grid containing 8 numbered tiles (from 1 to 8) and one empty space represented by 0. The objective is to rearrange the tiles into a specific goal configuration by sliding them one at a time.
Only tiles adjacent to the empty space (0) can be moved, and each move consists of swapping a tile with the 0.

Input Format
2D Array that contains initial state of the puzzle.

Output Format
Integer indicating minimum possible number of moves to solve the 8-Puzzle problem.
If the puzzle configuration is unsolvable, return -1.

A grid is considered solved if it is of the following configuration:

1 2 3
4 5 6
7 8 0

Sample Input
[[1,2,0],[4,5,3],[7,8,6]]

Sample Output
2

✅ English Summary (Short & Clear)

This is the classic 8-Puzzle shortest path problem.

✅ Approach

1. Convert the 3×3 grid to a 9-character string.
2. The goal state is "123456780".
3. Before BFS, compute inversion count to check solvability.
4. Use BFS to explore all valid moves by swapping 0 with its adjacent positions.
5. Track visited states to avoid cycles.
6. The level of BFS where the goal is found = minimum moves.

✅ Complexity

• Time: O(9!)
• Space: O(9!)

The VOprep team has long accompanied candidates through various major company OAs and VOs, including Microsoft Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Stripe or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.