滑块拼图
用 C++ 编写的滑块拼图生成器和求解器
该项目的最初目标是使用 A 星搜索算法创建滑块拼图生成器和求解器。 最初的方法使用树来存储棋盘状态,但是不断添加节点非常占用内存并最终崩溃。 我们决定采用贪心算法,利用曼哈顿距离计算来移动瓷砖。
该程序通过计算空瓷砖周围瓷砖的曼哈顿距离并进行最佳移动来工作,最佳移动是使瓷砖最接近其在棋盘上的原始位置的移动。 该程序继续使用曼哈顿距离挑选瓷砖,跟踪其最后一次移动以免重复。
该函数偶尔需要在无法找到最佳移动时强制移动以确保程序不会过早停止。 这会导致运动中的一些重复,但最终是必要的。
虽然它无法解决任何给定的谜题,但该程序可以处理大多数不同大小的谜题(3x3、4x4、5x5 等)。
2023-10-09 08:52:33
4KB
C++
1