微软面试题 #1 —— 8 数码拼图最少步数 – 微软面经 – Microsoft 面经 – VO辅助 – 代面试

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

总结（含解题思路）

这道题是经典的 8 拼图（8-Puzzle）最短步数搜索问题。

✅ 核心思路（简单但完整）

1. 将 3×3 拼图展开成 1×9 字符串，例如 "123405786"。
2. 目标状态固定："123456780"
3. 使用 BFS（宽度优先搜索） 寻找从起始状态到目标状态的最短步数：
   • 每次找到 0（空位）能交换的相邻位置
   • 交换生成新状态
   • 未访问过则入队
4. 如果 BFS 搜完还没到目标 → 返回 -1
5. 优化点：开始 BFS 前可以用 逆序数（inversions）判断是否可解

✅ 判断是否可解（重要）

将数组展开成一维，统计除了 0 以外的数字的逆序数。

• 逆序数为偶数 → 可解
• 逆序数为奇数 → 无解（直接返回 -1）

✅ 时间复杂度

• 最坏：状态数 9! = 362,880
• BFS 每个状态最多 4 步
  ✅ 时间复杂度：O(9!)（可接受）
  ✅ 空间复杂度：O(9!)

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括微软、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Stripe 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。