SlidingGame八数码难题破解BFS可解性判定的完整思路【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnbSlidingGame八数码滑块游戏是 AirBnB 面试题库中的经典搜索题给定 3×3 棋盘上的 8 个数字方块和 1 个空格通过滑动让棋盘在最少的步数内还原为目标格局。本文将BFS 广度优先搜索与可解性判定两大核心思路完整拆解所有讲解均可对照源码文件 SlidingGame.java 阅读。 八数码是什么30秒看懂题意八数码Eight Puzzle的规则非常简单3×3 棋盘上有 8 个编号为 1~8 的方块外加 1 个空格用 0 表示与空格相邻的方块可以滑入空格空格随之移动目标是通过一系列滑动把棋盘还原成指定的目标格局。以源码测试用例中的初始棋盘为例·代表空格初始棋盘 目标格局 3 1 4 0 1 2 6 2 · 3 4 5 7 5 8 6 7 8 小细节源码里定义的目标格局是 0~7 按行排列空格在左上角与常见的空格在右下角略有不同。这道题是题库第 18 题完整题目描述见 README.md。❓ 思路第一步这块棋盘有解吗可解性判定很多初学者上来就盲滑但八数码有个著名陷阱并非所有初始状态都能还原3×3 棋盘共有 9! 362,880 种布局其中恰好一半有解、一半无解。可解性判定有两种方案方案一BFS 穷举判定从初始状态逐层扩展所有可达状态若能找到目标格局说明可解若队列耗尽仍无新状态可扩说明无解。这就是源码中的canSolve()方法SlidingGame.java#L41-L88思路朴素但可靠3×3 状态空间极小直接跑满也很快。方案二数学奇偶判定瞬间出结果把棋盘方块按行序写成一个数字序列忽略空格统计逆序数大数在前、小数在后的数对个数。对于 3×3 棋盘有经典结论逆序数为偶数 → 有解逆序数为奇数 → 无解。用测试用例初始棋盘验证数字序列3 1 4 6 2 7 5 8的逆序数为 6偶数因此有解 ✅。该方法 O(n²) 完成判定、无需搜索是面试中高频的追问考点。 思路第二步用 BFS 找出最少步数确认有解后接下来就是如何用最少步数解开答案是BFS 广度优先搜索。核心技巧是把整个棋盘压缩成一个搜索状态状态表示把棋盘序列化成字符串如3,1,4,6,2,0,7,5,8源码通过getMatrixString()/recoverMatrixString()两个工具方法实现棋盘与字符串互转SlidingGame.java#L148-L167逐层扩展空格可向上下左右 4 个方向移动源码用方向向量dirs定义每移动一次就产生一个新棋盘状态visited 集合防环已访问的状态放入HashSet再次遇到直接跳过保证每个状态最多扩展一次避免死循环。由于 BFS 按步数一层一层扩展第一次遇到目标格局时这条路径必然最少步。源码的getSolution()SlidingGame.java#L90-L146就是在队列中额外携带路径信息每步记录 Down / Right / Up / Left命中目标时返回完整移动序列。方案适用场景特点BFS 逐层搜索3×3 八数码简单可靠保证找到最少步数逆序奇偶判定判断有解性瞬间出结果无需搜索A* 曼哈顿距离启发4×4 等大盘面速度快数量级需额外计算估价✅ 测试验证11 步完成还原内置单元测试SlidingGame.java#L170-L195对上述初始棋盘做了完整验证canSolve()返回truegetSolution()输出恰好11 步移动序列Left → Down → Left → Up → Up → Right → Right → Down → Left → Up → Left每一步都对应空格的一次移动11 次滑动后棋盘恰好到达0 在左上角的目标格局与 BFS最少步数的理论保证完全吻合。 快速上手自己跑一遍单元测试项目基于 Gradle 构建要求 Java 11 与 Gradle 5.6.3详见 README.md 的 Requirements 部分。克隆仓库后运行 SlidingGame 的测试git clone https://gitcode.com/gh_mirrors/ai/airbnb cd airbnb gradle -Dtest.singleSlidingGame test 延伸与面试追问十五数码4×4 版状态空间暴涨到 16!/2 ≈ 10.4 万亿纯 BFS 不可行标准解法是 A* 搜索用各方块到目标位置的曼哈顿距离之和作启发值双向 BFS从初始状态与目标状态同时向中间搜索搜索深度近似减半为什么不用 DFSDFS 虽能找到解但不保证步数最少且容易在死胡同里空转。总结八数码完整思路 可解性判定逆序奇偶 or BFS 穷举BFS 最短路径状态字符串编码 逐层扩展 visited 防环。掌握这套状态图搜索模型后迷宫最短路径、字谜滑动等同类题目都能举一反三。【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考