10

无论使用哪种布局，有没有什么好的方法来分配瓷砖，以便您可以向用户保证，在游戏开始时，至少存在一条完成拼图并赢得游戏的途径?

显然，根据用户的动作，他们可以切断自己的胜利。我只想能够总是告诉用户，如果他们玩得好，这个谜题是可以赢的。

如果您在游戏开始时随机放置瓷砖，则用户可能会移动一些动作而无法再移动。一个谜题至少可以解决的知识应该让它更有趣。

4

8 回答 8

19

将所有瓷砖反向放置（即从中间开始布置板，锻炼）

为了进一步逗弄玩家，您可以以非常高的速度明显地做到这一点。

于 2008-10-01T20:29:29.500 回答
10

反过来玩游戏。

在您可以将它们滑入堆中的地方，一对对地随机放置碎片。你需要一种方法来知道你可以在哪里放置碎片，以便最终得到一个与某些预设模式匹配的堆，但无论如何你都需要它。

于 2008-10-01T20:30:13.537 回答
8

我知道这是一个老问题，但我自己解决问题时遇到了这个问题。这里没有一个答案是非常完美的，其中一些有复杂的警告或将打破病态布局。这是我的解决方案：

用未标记的瓷砖解决棋盘（向前，而不是向后）。一次移除两个空闲的瓷砖。将您删除的每一对推入“匹配对”堆栈。通常，这就是您需要做的所有事情。

如果您遇到死胡同（numFreeTiles == 1），只需重置您的生成器 :) 我发现我通常不会遇到死胡同，并且到目前为止 10 次左右的最大重试次数为 3我尝试过的布局。一旦我重试了 8 次，我就放弃了，只是随机分配其余的图块。这使我可以使用相同的生成器来设置棋盘和随机播放功能，即使玩家搞砸了并进入了 100% 无法解决的状态。

当您遇到死胡同时，另一种解决方案是退出（弹出堆栈，替换板上的瓷砖），直到您可以采取不同的路径。通过确保匹配将删除原始阻挡瓷砖的对来采取不同的路径。

不幸的是，根据董事会的不同，这可能会永远循环。如果您最终删除了一条类似于“无出口”道路的对，其中所有后续“道路”都是死胡同，并且有多个死胡同，那么您的算法将永远不会完成。我不知道是否有可能在这种情况下设计一个电路板，但如果是这样，仍然有一个解决方案。

为了解决这个更大的问题，将每个可能的棋盘状态视为 DAG 中的一个节点，每个选定的对都是该图上的一条边。进行随机遍历，直到找到深度为 72 的叶节点。跟踪您的遍历历史，这样您就不会重复下降。

由于死角比我使用的布局中的第一次尝试解决方案更罕见，因此立即想到的是混合解决方案。首先尝试用最少的内存来解决它（将选定的对存储在堆栈中）。一旦你遇到了第一个死胡同，在访问每个节点时降级为进行完整的标记/边缘生成（可能的惰性评估）。

不过，我对图论的研究很少，所以也许对 DAG 随机遍历/搜索问题有更好的解决方案:)

编辑：你实际上可以使用我的任何解决方案来反向生成板，ala 2008 年 10 月 13 日的帖子。你仍然有同样的警告，因为你仍然可能会陷入死胡同。但是，反向生成棋盘具有更复杂的规则。例如，如果您没有从中间的第一部分开始至少一些行，例如在带有 1 个长行的布局中，那么您肯定会失败您的设置。在正解生成器中选择完全随机（合法）的第一步更有可能导致可解的棋盘。

于 2009-12-16T02:16:17.497 回答
5

我唯一能想到的就是将棋子成对放置，就像一种反向麻将纸牌游戏。因此，在放置瓷砖的任何时候，棋盘都应该看起来像是在真实游戏的中间（即没有瓷砖漂浮在其他瓷砖上方 3 层）。

如果棋子在反向游戏中成对放置，则应始终产生至少一条正向路径来解决游戏。

我很想听听其他想法。

于 2008-10-01T20:31:18.137 回答
0

我相信最好的答案已经被推高了：通过“反向”解决它来创建一个集合 - 即从一个空白板开始，然后在某处添加一对，在可解决的位置添加另一对，等等......

如果您更喜欢“大爆炸”方法（在开始时随机生成整个集合），是一个非常有男子气概的开发人员，或者今天只是觉得自虐，您可以表示您可以从给定集合中取出的所有对以及它们如何依赖通过有向图相互连接。

从那里，您只需要获得该集合的传递闭包，并确定是否至少有一个从至少一个初始合法对到所需结束的路径（没有剩余的瓦片对）。

实施此解决方案留给读者作为练习：D

于 2008-10-01T21:42:01.837 回答
0

这是我在实现中使用的规则。

在构建堆时，对于一对中的每个品格，分别找到一个单元格（位置），它们是：

  • 已填充较低级别的所有单元格
  • 考虑到第一个品格是否已经装上，第二个品格的位置不会首先阻塞
  • 这两个地方都在已经构建的堆的“边缘”：
    • EITHER 在左侧或右侧至少有一个邻居
    • 或者它是连续第一个烦恼（左右的所有单元格都是递归自由的）

这些规则并不能保证构建总是成功 - 它有时会留下最后 2 个空闲单元自阻塞，并且应该重试构建（或至少最后几个烦恼）在实践中，“乌龟”构建不超过 6 次重试。

大多数现有游戏似乎都将第一排（“第一排”）音品限制在中间的某个位置。这提供了更方便的配置，当非常长的行的边缘没有音品时，一直到最后一个玩家移动。但是，“中间”对于不同的配置是不同的。

祝你好运 ：）

PS如果您发现可以一次性构建可解堆的算法 - 请告诉我。

于 2008-10-13T07:49:19.720 回答
0

您在游戏中有 144 个图块，144 个图块中的每一个都有一个阻止列表..（堆栈顶部的图块有一个空的块列表）

所有有效的移动都要求它们的“current__vertical_Block_list”为空。这可以是一个 144x144 的矩阵，所以 20k 的内存加上一个 LEFT 和 RIGHT 块列表，每个也是 20k。

从 (remaning_tiles) A​​ND ((empty CURRENT VERTICAL BLOCK LIST) and ((empty CURRENT LEFT BLOCK LIST) OR (empty CURRENT RIGHT BLOCK LIST))) 生成有效的移动表

从有效移动表中随机选择 2 个图块，记录它们更新（当前表 Vert、左和右），将移除的图块记录到堆栈

现在我们有一个构成有效游戏的动作列表。为 72 个动作中的每一个分配匹配的瓷砖类型。

对于具有挑战性的游戏，跟踪每个图块何时可用。找到具有 (early early early late) 和 (late late late early early) 的集合，因为它是空白的，你会发现 1 EE 1 LL 和 2 LE 块.. 在 2 LE 块中，找到一个 EARLY 可以阻止任何其他 EARLY （除了右挡住左边的棋子）
一旦你得到了一个有效的游戏，就可以按照顺序玩。

于 2010-01-28T07:16:36.213 回答
-1

纸牌？只是一个猜测，但我认为您的计算机需要击败游戏（或接近游戏）才能确定这一点。

另一种选择可能是有几个预设布局（允许获胜，与您当前的水平混合。

在某种程度上，您可以尝试确保 4 个图块之一不超过另一个 X 下方的 X 层。

我看到的大多数游戏都有 shuffle 命令用于当有人卡住时。

我会尝试多种方法，看看哪种效果最好。

于 2008-10-01T20:33:30.410 回答