Microsoft VO 面试真题解析：8-Puzzle（滑动拼图最少步数）

8-Puzzle

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 the initial state of the puzzle.

Output Format

Integer indicating the 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-Puzzle 滑动拼图最少步数问题。由于每次只能把与空格 0 相邻的数字交换位置，状态空间可以建模为图上的节点，使用 BFS 搜索即可找到从初始状态到目标状态的最短步数；如果加入可达性判断，也可以先用逆序数判断是否无解，避免无效搜索。题目中的目标状态是 1 到 8 依次排列，空格在右下角，样例 [[1,2,0],[4,5,3],[7,8,6]] 到目标只需 2 步，因此输出为 2。