logo标签列表

解决Flow Free游戏的算法

algorithmgraphartificial-intelligence
22

最近我开始玩Flow Free Game。

连接相同颜色的管道以创建流。将所有颜色配对，并覆盖整个板块以解决 Flow Free 中的每个难题。但要小心，如果管道交叉或重叠，它们会断裂！

我意识到这只是在给定点对之间寻找路径的游戏，条件是没有两条路径重叠。我想写一个解决方案来玩这个游戏，但不知道从哪里开始。我考虑使用回溯法，但对于非常大的棋盘大小，它的时间复杂度将很高。

有没有适合有效解决这个问题的算法？使用启发式方法解决问题是否有帮助？只要给我一个提示，我就会从那里开始。

我观察到在大多数版中通常：

  1. 对于最远的点，您需要沿边缘走。
  2. 对于彼此最近的点，如果有直接路径，请沿着直接路径走。

这个观察是否正确，且是否能用于有效解决问题？

2
关键词是“大多数棋盘”。Free Flow是一个已知的NP-Hard（如果不是NP-Complete）游戏的视觉现代化，我无法立即想到它的名称。因此，在所有情况下都没有有效的解决方案是未知的和预期的，如果您尝试解决更大的问题，则更容易看出这一点。 - Nuclearman
1
不，没有有效的解决方案。计算机可以解决Free Flow的任何实例，但平均所需时间随着谜题规模呈指数增长。粗略估计可能会说，例如10x10的难度大约是5x5的30倍。我在实践中看到了这一点，因为我可以在不到一秒钟的时间内解决5x5的难题，但通常需要更长时间来解决10x10的难题。同时，20x20的难度可能比10x10的难度高出约1000倍。虽然Free Flow中没有20x20的难题，但我已经解决了该游戏中的所有难题，其中一些难题花费了很多时间。 - Nuclearman
1
@Nuclearman 我认为这是多商品流的特殊情况，但这并不一定意味着它是 NP-hard。 - templatetypedef
@templatetypedef：我花了一些时间才找到它，但是这里是我第一次遇到它的地方。在线上进行了一些研究似乎证实了这一点。我想的游戏是NumberLink。我记得它是由著名的日本游戏发行商Nikoli发布的，我就是通过这种方式找到了它的名字。 - Nuclearman
@ziggystar：搜索“Numberlink的SAT公式”和“Numberlink的NP完备性”会得到一些参考资料。毫不奇怪，其中最有趣的两个是用日语写的。第一个是NP完备性的实际证明论文。第二个描述了如何使用SAT求解器Sugar来解决NumberLink问题。 - Nuclearman
显示剩余4条评论
6个回答
8

化简为SAT问题

基本思路

  1. 将问题化简为SAT问题
  2. 使用现代SAT求解器来解决问题
  3. 获得收益

复杂度

该问题显然属于NP问题：如果你猜测了一个棋盘的组合，检查它是否解决了问题很容易（多项式时间）。

它是否是NP难问题（意味着与NP中的其他问题一样困难，例如SAT），尚不清楚。当然，现代的SAT求解器不会在乎并且可以轻松地解决大规模实例（我猜最多100x100）。

关于数字连线的文献

这里我只是复制了Nuclearman对OP的评论：

搜索“NumberLink的SAT公式”和“NumberLink的NP完全性”会得到几个参考文献。毫不意外，其中最有趣的两篇是用日语写的。first 是 NP 完全性的实际论文证明。second 描述了如何使用 SAT 求解器 Sugar 来解决 NumberLink 问题。

约简为 SAT 的提示

有几种可能的编码方式可以解决这个问题。我会很快给出一种。

备注

j_random_hacker 指出，不允许自由环。以下编码允许它们。这使得 SAT 编码的可行性稍微下降了一些。我能想到的最简单的方法是引入 O(n^2) 个新变量，其中n 是棋盘上的方块数（对每个方块计算到下一个汇点的距离）除非使用对数编码，将其降至O(n*log n)，可能会使求解器难以处理。

变量

每个方块、棋子类型和颜色对应一个变量。例如，如果某个变量X-Y-T-C为真，则表示位置X/Y的方块类型为T且颜色为C。由于空白方块在解决方案中不会出现，因此您不需要空白方块类型。

设置初始变量

为汇点/源点设置变量，并指定其他方块不能成为汇点/源点。

约束条件

  1. 对于每个位置，只有一种颜色/棋子组合是正确的（基数约束）。
  2. 对于每个变量（位置、类型、颜色），四个相邻方块必须兼容（如果颜色匹配）。

我可能遗漏了一些内容，但这很容易修复。

有关如何将问题简化为SAT的任何建议？ - coder hacker
不错的解决方案！我认为你可以以同样的方式将其简化为整数线性规划(ILP)，然后使用标准求解器。约束条件是：每个源/汇点都有1或3个相同颜色的邻居，其他每个单元格都有2或4个相同颜色的邻居。未解决问题：正式证明符合这些约束条件的解决方案是有效的。通过反证法来证明应该不难。 - Vincent van der Weele
@Heuster 虽然将其简化为整数线性规划问题是可行的，但我不建议这样做。这不是一个优化问题，而只是一个满足性问题。使用CSP格式可能比SAT更方便使用。SAT和CSP之间的区别在于CSP允许具有多个值的变量。 - ziggystar
@ziggystar 没错，你说得对，这不是真正的优化问题。 - Vincent van der Weele
请看我的回答，了解如何使用 SAT 解决它。 - Pro Q
显示剩余2条评论
4
我怀疑没有多项式时间算法可以保证解决这个问题的每一个实例。但是由于要求每个正方形都必须被管道覆盖，因此类似于人类和计算机用于解决数独的方法在这里应该很有效：
1. 对于每个空白正方形，形成该正方形可能颜色的集合，然后在每个正方形上重复执行逻辑推断，以缩小该正方形允许的颜色集。 2. 每当正方形的可能颜色集缩小到大小为1时，该正方形的颜色就确定了。 3. 如果我们达到了一个状态，在这个状态中不能再进行逻辑推断，并且谜题还没有完全解决（即至少有一个正方形具有多个可能的颜色），则选择其中一个未决定的正方形并对其进行递归，依次尝试每种可能的颜色。每次尝试将导致解决方案或矛盾；后者会消除该颜色作为该正方形可能性。
在选择分支正方形时，通常最好选择允许颜色最少的正方形。
[编辑：避免形成无效的“管道回路”非常重要。一种方法是为每个正方形x的每个允许颜色i维护2位信息：正方形x是否通过一条明确的i-颜色瓷砖路径与第一个i-颜色端点连接，以及同样的内容适用于第二个i-颜色端点。然后在进行递归时，不要选择具有两个相同位设置（或没有位设置）的邻居的正方形，对于任何允许的颜色。]
实际上，您根本不需要使用任何逻辑推断，但是您使用的推断越多且越好，程序运行得越快，因为它们将（可能显着）减少递归量。一些有用的推断包括：
1. 如果某个正方形是扩展某个特定颜色路径的唯一可能方法，则必须分配该颜色。 2. 如果某个正方形在其允许的颜色集中具有颜色i，但它没有至少有2个相邻正方形也在其允许的颜色集中具有颜色i，则它无法被任何i颜色的路径“到达”，并且可以消除颜色i作为可能性。
基于路径连通性的更高级别的推断可能会进一步帮助 - 例如，如果您可以确定连接某对连接器的每条路径都必须通过特定的正方形，则可以立即将该颜色分配给该正方形。
这种简单的方法在您的5x5示例中推断出完整的解决方案，而无需任何递归：位于（5,2）、（5,3）、（4,3）和（4,4）的正方形被迫变为橙色；（4,5）被迫变成绿色；由于没有其他颜色能够到达这个方块然后再返回来，（5,5）也被迫变成绿色。现在，以（4,4）结束的橙色路径除了完成（3,4）处的橙色路径之外，别无选择。此外，（3,1）被迫变成红色；（3,2）被迫变成黄色，进而迫使（2,1）和（2,2）变成红色，最终迫使黄色路径在（3,3）处完成。在（2,2）处的红色管道迫使（1,2）变成蓝色，红色和蓝色路径最终被完全确定，“相互迫使”。
如果您使用SAT求解器，它将执行本答案中描述的所有操作，以及更多（您甚至没有想到的事情）。 - ziggystar
@ziggystar：告诉一个SAT求解器需要避免管道循环可能会很困难。对于从TSP中消除子路径，通常是通过在发现必要时即时生成这些约束来处理的，因为它们的数量呈指数级增长，因此在开始时指定所有约束将是不可行的。（这使用了一个ILP求解器，但情况类似。） - j_random_hacker
那么，a) 游戏中是否可能出现循环？b) 它们是否被禁止？这不是最短路径竞赛。它是 将所有的碎片拼合在一起 。如果你根本不能有循环/交叉，那么就不允许相应的碎片。 - ziggystar
@DavidEisenstat 我同意你的观点，你可以潜在地进行比SAT求解器更多的传播（人们发现除了单元传播之外的任何复杂操作都不划算），特别是你可以按照领域依赖的方式来实现。但这并不简单，而且可能不会更快。我想我基本上想说的是：将问题规约为SAT问题很容易，也是我首先尝试的事情。此外，不清楚你是否能够在合理的时间内实现更快的算法。但如果你喜欢编程，当然可以继续尝试。 - ziggystar
@ziggystar：在我找到的在线游戏版本中，你不能创建独立的循环。不确定你所说的“然后不允许相应的部件”是什么意思 - 你会怎么做？ - j_random_hacker
显示剩余3条评论
4

我在Needlessly Complex上找到了一篇博客文章，完全解释了如何使用SAT来解决这个问题。

代码也是开源的，所以你可以查看它（并且理解它）的实际操作。

以下是一段描述在SAT中需要实现的规则的引用：

  • 每个单元格分配一个颜色。

  • 每个端点单元格的颜色已知并指定。

  • 每个端点单元格有一个与其颜色相匹配的邻居。
  • 通过每个非端点单元格的流量恰好匹配六种方向类型之一。
  • 由其方向类型指定的单元格的邻居必须与其颜色相匹配。
  • 未由其方向类型指定的单元格的邻居不能与其颜色相匹配。

感谢@Matt Zucker创建了这个工具！

如果旧链接失效，可以使用 Wayback Machine 的链接：https://web.archive.org/web/20180607162803/https://mzucker.github.io/2016/09/02/eating-sat-flavored-crow.html - Pro Q
0

我喜欢类似于人类思维的解决方案。你可以通过暴力方法轻松地得到数独的答案，但更有用的是获得你可以遵循的路径来解决难题。

我在大多数棋盘中观察到通常 1.对于最远的点，您需要沿着边缘走。 2.对于彼此最近的点，如果有直接路径，请沿着直接路径走。 这个观察是否正确，能否有效地解决它？

这些“大多数情况下”是正确的，但并非总是如此。

我会用这个规则替换你的第一个规则：如果两个汇点都在边缘上，你需要沿着边缘走。（你可以构建一个反例，但大多数情况下是正确的）。在你沿着边缘走过一条路径之后，沿着边缘的块应该被视为边缘的一部分，因此你的算法将尝试跟随前一个管道所形成的新边缘。我希望这句话有意义……

当然，在使用这些“大多数情况下”的规则之前，你需要遵循绝对的规则（请参见j_random_hacker的帖子中的两个推论）。

另一件事是尝试消除不能导致解决方案的棋盘。我们称未完成的管道（从水槽开始但尚未到达另一个水槽的管道）为蛇，未完成的管道的最后一个方块将被称为蛇头。如果您找不到两个相同颜色的蛇头之间的空白方块路径，则意味着您的棋盘无法导致解决方案，应该丢弃它（或者根据您的实现进行回溯）。

自由流游戏（以及其他类似的游戏）接受两行相同颜色并排放置作为有效解决方案，但我相信总存在一种没有相邻行的解决方案。这意味着任何不是水槽的方块都有恰好两个相同颜色的邻居，而水槽则恰好有一个。如果规则恰好始终成立（我相信是这样，但无法证明），那将是减少可能性的额外约束条件。我使用了相邻行来解决一些自由流难题，但大多数情况下我找到了另一种解决方案而没有使用相邻行。我在自由流解决方案网站上没有看到过相邻行。

0

根据Big Duck Games的IOS版本，有一些规则可以导致一种算法来解决Flow中的关卡，这家公司似乎生产了标准版本。本答案的其余部分假设没有墙壁、桥梁或扭曲。

即使你非常聪明，巨大的15x18方形棋盘也是一个很好的例子，说明仅仅按照看起来可能的方式去尝试会让你在接近结尾时反复陷入困境，实际上不得不从头开始。这可能与一般情况下已经提到的指数时间复杂度有关。但这并不意味着简单的策略对于大多数棋盘不是极其有效的。

  1. 方块永远不会空着，因此孤立的方块意味着你做错了什么。

  2. 相邻的同色单元格必须连接。这排除了相邻的2x2同色方块和六边形网格上三个相邻单元格的三角形。

  3. 通过确定某个颜色进入或排除某个特定的方格，通常可以取得永久性的进展。

  4. 由于第1点和第2点，在形状为六边形的板子上，沿着边缘走的管道通常会一直沿着边缘走到出口，有效地将外边缘移动并使板子变小，以便重复该过程。对于两种类型的网格，可以预测哪些相邻条件保证和哪些条件会打破这个循环。

我发现大多数第三方变体都缺少1到4，但考虑到这些限制，生成有效的板子可能是一项困难的任务。

答案：

第三点建议为每个单元格存储一个值，该值可以是颜色或一组假/不确定值，其中每种颜色都有一个。

求解器可以反复使用点1和点2以及存储在点3中的数据，在管道末端周围的小邻域路径上逐渐设置颜色或将不确定值设置为假。

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