如何在代码中以编程方式创建有效的 15 谜题

Question

我已经用 JS 构建了 15 个谜题，但我的随机谜题生成正在创建无法解决的谜题的实例。这可能是因为我不是计算机科学的负责人，但我不确定如何计算代码中排列中的反转数量之类的问题。我想知道如何编写我的代码，以便我可以测试我的谜题的任何给定开始状态是否都是可解决的。我在已发布的应用程序中看到了其他 15 个无法解决的谜题，所以看来我并不是唯一一个遇到这个问题的人。

我已经看过这篇文章，但它仅限于 CS 级别，我正在寻找一个代码实现来帮助我更好地理解这一点： 15 Puzzle Heuristic

我正在使用 JS，但无论哪种语言的任何帮助和解释都会有很大帮助。

Answer 1

可解性算法基于反演奇偶校验，并在15 Puzzle - Wolfram Math World中进行了解释转换成代码应该不会太困难。 IIRC 在不可解的起点上交换两个相邻的方块使其可解，但您需要确认这一点。

请注意，这是确定谜题是否可以解决的精确算法，而不是用于指导解决方案中的步骤顺序的启发式算法。

Answer 2

我在评论中回避的内容，但不确定这是否是正确的方法：

1. 从“正确的”15位序列/板开始
2. 生成随机数的“错误放置”您可以向棋盘申请
3. 根据您生成的随机数生成 N 个有效的错失位置列表
4. 您现在应该有一个有效的游戏。

因为你从一个有效的棋盘开始，然后应用一组强制的错误方向，所以你总是会得到一个完全合法的开始游戏。