logo标签列表

麻将 - 安排牌以确保至少有一条通向胜利的路径，无论布局如何

algorithmmahjong
10
无论使用何种瓷砖布局，有没有一种好的方法来分配瓷砖，以便您可以保证在游戏开始时存在至少一条路径来完成谜题并赢得游戏？
显然，根据用户的动作，他们可能会失去获胜的机会。我只想告诉用户，如果他们玩得好，这个谜题是可以赢的。
如果您在游戏开始时随机放置瓷砖，则有可能用户做几个动作后就无法继续。知道一个谜题至少有解决方案应该使其更有趣。
8个回答
20

将所有瓷砖倒置（即从中间开始布局，向外扩展）。

为了更进一步刺激玩家，可以让其在非常高速的情况下进行可见操作。

1
这并不保证胜利，你仍然可能会遇到一些无法获得的情况，例如ABAB - 在你获得B之前没有办法获得A，反之亦然。 - 1800 INFORMATION
1
如果你以相反的方式“玩”这个游戏，那么形成这种排列将是不可能的，除非两个A实际上是两对中的一部分，其中玩家之前移除了“错误”的一个。 - Lasse V. Karlsen
请注意，如果您以这种方式操作，需要将方块成对放置而不是逐个放置。如果您先放置一个方块，然后将其对应的方块直接放在其上面，仍然可能创建无法获胜的情况。（或者您可以编写代码来明确排除此可能性。） - Ryan Lundy
10

反向玩游戏。

随机成对地摆放碎片，在可以滑动到堆中的位置。您需要一种方法来“知道”您可以放置碎片的位置，以便最终获得与某些预设模式匹配的堆，但无论如何都需要这样做。

很抱歉，我无法花足够的时间来解决这个问题。我宁愿避免在编辑伪代码后进入“好吧，但你考虑过……”的评论讨论中，从而不时将一个11年前的问题推到首页。 - Lasse V. Karlsen
抱歉。我写了一些代码来生成套装，但有时会陷入死局。所以我想知道如何反向生成套装。 - caochao
8
我知道这是一个老问题，但我在解决自己的问题时遇到了这个问题。这里没有一个完美的答案，其中几个有复杂的警告或将在病态布局上中断。以下是我的解决方案：
使用未标记的图块解决板（向前，而不是向后）。每次删除两个空闲的图块。将您删除的每对推入“匹配对”堆栈。通常，这就是您所需要做的。
如果遇到死路（numFreeTiles == 1），请重置生成器:)我发现我通常不会遇到死路，并且迄今为止最大的重试次数为我尝试过的10个左右的布局的3次。一旦我达到8次重试，我就放弃并随机分配其余的图块。这使我可以为设置板和洗牌功能使用相同的生成器，即使玩家出错并创建了100％无法解决的状态。
当您遇到死路时，另一种解决方案是退出（从堆栈中弹出，替换板上的图块），直到您可以走另一条路。通过确保您匹配将删除原始阻塞图块的对来走另一条路。
不幸的是，根据板子的情况，这可能会永远循环。如果您最终删除了一个类似于“无出口”道路的对，其中所有后续的“道路”都是死路，并且存在多个死路，则您的算法永远不会完成。我不知道是否可能设计一个这种情况的板子，但如果是这样，仍然有解决方案。
为了解决更大的问题，请将每个可能的板状态视为DAG中的一个节点，其中每个选择的对都是该图形上的边缘。进行随机遍历，直到在深度为72的叶节点处找到一个。跟踪您的遍历历史记录，以便您从不重复下降。
由于死路比我使用的布局中的第一次尝试解决方案更少，因此立即想到的是混合解决方案。首先尝试使用最小内存解决它（在堆栈上存储所选对）。一旦您达到第一个死路，请降级以在访问每个节点时执行完整的标记/边缘生成（在可能的情况下进行懒惰评估）。
我几乎没有研究过图论，所以也许有更好的解决方案来解决DAG随机遍历/搜索问题：）
编辑：实际上，您可以使用任何一种生成反向板的解决方案，例如2008年10月13日发布的帖子。您仍然有相同的注意事项，因为您仍然可能遇到死路。反向生成板具有更复杂的规则。例如，在至少一些行中以第一个图块开始，例如在具有1个长行的布局中，如果您不从中间开始选择完全随机的（合法）第一步，则保证失败设置。在前向解算器中选择完全随机的第一步更有可能导致可解决的板。
2
这个可能有点老了，但我只是为了提高我的声望才回来给它点赞。反向求解存在许多问题，而使用这种正向方法求解既容易又具有其他用例，正如你所提到的那样。这是正确的方法。 - DannyB
（C）当您将两个瓷砖放入空行时，只需将它们放在一起即可。我想这就是全部内容了。使用此方法，您不应该会遇到死路。 - blubberdiblub
1
@blubberdiblub - 举个例子，一种病态情况是：4个插槽都在一排中相邻。如果你随机放置两个符合规则（C）的方块，则有2:3的几率需要违反规则（B）才能继续，这样你就会得到一个无解的棋盘。你的算法对于僵局情况有什么规定？ - Merlyn Morgan-Graham
1
回复这个古老的帖子：这似乎是正确的答案。有人在2007年写了一篇研究论文，提供了伪代码，并详细讨论了整个主题：http://iivq.net/scriptie/scriptie-bsc.pdf - katzenklavier
1
@edave 当然。我试图在你引用的段落之后说了和你一样的话，但是因为我的信心不足，我的写作变得不清晰。遍历DAG（彻底，无重复）。没有用于选择路径的启发式方法。这是蛮力算法的典范 :) - Merlyn Morgan-Graham
显示剩余3条评论
5

我唯一想到的方法是将瓷砖放置在匹配的成对位置，就像倒着玩麻将接龙一样。因此，在放置瓷砖的任何时刻，游戏板应该看起来像是处于真正游戏的中间阶段（即没有瓷砖浮动在其他瓷砖上方3层）。

如果将瓷砖放置在匹配的成对位置并进行倒着玩，它应该始终会有至少一条正向路径来解决游戏。

我很乐意听取其他的想法。

天啊...这些人速度真快！太棒了。我刚发布完问题就立即开始回答，结果提交时已经有两个答案了。 - Buns of Aluminum
那，我的朋友，就是 <booming_voice>STACKOVERFLOW</booming_voice> 的威力。 - Wes P
0

游戏中有144个方块，每个方块都有一个块列表。 （堆栈上的顶部方块具有空块列表）

所有有效移动都要求它们的“current__vertical_Block_list”为空。这可以是一个144x144矩阵，因此需要20k的内存以及左侧和右侧的块列表，每个也需要20k。

从（剩余的方块）和（（空的CURRENT VERTICAL BLOCK LIST）和（（空的CURRENT LEFT BLOCK LIST）或（空的CURRENT RIGHT BLOCK LIST）））生成一个有效的移动表。

从有效的移动表中随机选择2个方块，并记录它们。更新当前表格的Vert、left和right，并将删除的方块记录到堆栈中。

现在我们有了一个包含有效游戏的移动列表。为每个72个移动分配匹配的方块类型。

对于具有挑战性的游戏，请跟踪每个方块何时可用。找到早期早期晚期和晚期晚期早期的集合，因为它是空白的，所以你会发现1个EE 1个LL和2个LE块。在2个LE块中，找到一个EARLY，它会阻止除右侧块之外的任何其他EARLY块（左侧块）。
一旦你获得了一个有效的游戏，请尝试改变顺序。

0

我相信最好的答案已经被推出来了：通过“反向”解决问题创建一个集合 - 即从一个空白的棋盘开始，然后在某个位置添加一对，再添加另一对可解的位置，以此类推...

如果你更喜欢“大爆炸”方法（在开始时随机生成整个集合），是一个非常“男人”的开发者或者今天只是感到自虐，那么你可以通过有向图表示从给定集合中可以取出的所有对及它们之间的依赖关系。

从那里，你只需要获取该集合的传递闭包，并确定是否存在至少一条路径从至少一个初始合法对导致所需的结果（没有剩余的瓷砖对）。

实现这个解决方案留给读者作为练习:D

0

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

在构建堆时，对于每对fret分别找到一个单元格（位置），它们应该满足以下条件：

  • 所有较低级别的单元格都已经填满
  • 考虑第一个fret已经放置在板子上的情况下，第二个fret的位置不会挡住第一个fret
  • 两个位置都处于已构建堆的“边缘”：
    • 要么至少有一个左侧或右侧的邻居
    • 要么是一排中的第一个fret（所有左侧和右侧的单元格都是递归空闲的）

这些规则并不能保证构建总是成功的 - 有时会留下最后2个自相矛盾的空单元格，需要重新尝试构建（或至少是最后几个fret） 在实践中，“turtle”最多只需6次重试即可完成构建。

大多数现有游戏似乎限制将第一个（“行首”）fret放在中间某个位置。这会产生更方便的配置，当没有fret位于非常长的行的边缘时，可以一直保持到最后一个玩家移动。但是，“中间”对于不同的配置是不同的。

祝好运 :)

P.S. 如果您发现了可以在一回合内构建可解堆的算法，请告诉我。

-2

纸牌游戏？ 我猜测您的计算机需要打赢这个游戏（或接近于打赢）才能确定这一点。

另一种选择可能是拥有几个预先设置的布局（允许赢得，混合您当前的水平）。

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

我看到的大多数游戏都有洗牌命令，以便当有人卡住时使用。

我会尝试组合各种方法，看看哪种最有效。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接