学习目标与前置知识

• 明确搜索状态、合法选择与终止条件，完成能通过本地判题的 C++17 解答。
• 用边界输入解释本题的常见错误，说明剪枝或最短距离为何正确。
• 前置：本章相关知识，C++ 函数、容器、递归，以及题目所用的队列或位运算。

题目描述

一个3×3棋盘放有数字1到8和一个空格。每次可将空格与上下左右相邻的数字交换。给定初始状态，求最少多少步可以变成目标状态 123804765，即下面的棋盘：第一行123，第二行804，第三行765。

本 Lab 保留原题的标准输入/输出合同。

目标棋盘

1 2 3
8 0 4
7 6 5

输入格式

一行九字符状态，从上到下、从左到右排列，0表示空格。

输出格式

输出到达目标状态所需的最少交换次数。

数据范围

输入恰好包含0到8各一次，原题保证初始状态能到达目标。最前面的0必须保留。

样例输入

283104765

样例输出

4

状态与边界

整个九字符棋盘才是一个状态，不能只以空格位置判断是否访问；BFS按交换次数分层。

目标是123804765而不是常见的123456780；用字符串读取，避免前导0被吞掉。

复杂度目标

可达状态数不超过9!/2，每个最多4条边，时间 O(9 * 9!)，空间 O(9 * 9!)；9为编码和复制状态的成本。

编写与测试

修改 student/main.cpp 中的 solve，保留读写框架。标准输出只保留答案，调试信息写入标准错误。测试清单和分值以 tests/cases.json 为准，总分 100 分，输入均符合本页约定。

在仓库根目录执行：

pnpm lab:run -- labs/chapter-15/exercise/E-15-18-eight-puzzle
pnpm lab:score -- labs/chapter-15/exercise/E-15-18-eight-puzzle

进入本 Lab 目录后也可以运行 make run。作者与 CI 严格核验：

pnpm lab:verify -- labs/chapter-15/exercise/E-15-18-eight-puzzle

完成清单

• 学生程序编译成功，严格评分为 100/100。
• 能解释搜索状态、终止、撤销或剪枝，以及复杂度。
• 构造一个能击穿常见错误的最小输入。
• 答案的数量、顺序和空结果处理符合本页约定。

思考与复盘

1. 哪些信息必须随当前路径恢复，哪些信息可以保留？
2. 去掉本题的一条约束或剪枝，会影响正确性还是只影响效率？请用具体输入说明。
3. 输入达到上限时，时间、递归深度和输出大小分别如何增长？

题目来源与课程化说明

来源：洛谷 P1379 八数码难题。题面按课程环境重新表述，参考实现和测试独立编写，不复制第三方题解或隐藏测试。完整参考代码位于 solution/main.cpp。