26

现在是星期五下午，让我们来解决一个有趣的拼图/算法问题。

我最喜欢的任天堂 DS 游戏之一是Picross DS。游戏非常简单，它涉及解决称为Nonograms的谜题。您可以在这里尝试一个简单的在线 Picross 克隆：TylerK 的 Picross。

非图是一个网格，为网格的每一行和每一列定义了数字序列。这些数字定义了该行/列的“填充”方块块，但未定义块两侧的未填充区域。例如，如果您有一行如下所示：


（来源：steam-punk.net）

该行的可能解决方案包括：


（来源：steam-punk.net）（来源：steam-punk.net）

等等

“4 5”只是告诉您，在该行的某处，有 4 个连续块填充，然后是 5 个连续块填充。这些将是唯一填充的块，它们之前/之后的空间量是没有定义的。

当所有行和列都满足其定义且没有任何矛盾时，拼图就完成了。

概念上非常简单的游戏，但手动解决其中一些可能需要相当长的时间。Picross DS 的谜题逐渐增大到 25x20 的网格，这通常需要我大约半小时才能解决。

然而，我总是想到，编写一个程序来解决这将是一个非常简单的游戏。我从来没有接触过它，但也许这里的一些人会喜欢这个挑战。如果发布了相当数量的解决方案，我将在一个大谜题上对它们进行基准测试，类似于Paolo Bergantino 在这里用他的 Boggle question 所做的。Nonogram Wikipedia 页面上有很多关于破解谜题的方法的信息，如果你想参考的话。

这是来自 TylerK 的 Picross 的 Puzzle #1 的易于解析的定义，因此您可以为程序提供一些内容。第 1 行是拼图尺寸（可能不需要），第 2 行是行定义，第 3 行是列定义。这只是想到的第一件事，所以如果有人能想到更好的输入格式，请随时评论或编辑这篇文章以包含它。

15 15
15,4 5,2 4,1 3,2,2,2 4 3,2 6 2,2 1 6 2,2 1 1 4 2,1 1,1 3 2 1,2 2 1 2 1,3 3 2 1,9
4 4,3 1 2 3,2 1 2 2,2 1 1,1 4 2,1 3,1 8,1 3 1 1,1 4 2 1,1 4,2 4 3,3 3 3,4 1,10 3,10
4

10 回答 10

22

是的，问题是 NP 完全的，但这仅意味着随着拼图规模的增长，您（几乎）陷入了指数级增长的运行时间。但在现实生活中，拼图大小不会增长。几乎没有人会费心制作大于 100x100 且绝大多数小于 50x50 的拼图。构建一个能够在几分之一秒内解决书籍和杂志中 95% 的谜题的求解器实际上并不是特别具有挑战性。一个相当直接的深度优先搜索系统可以做到这一点。

不太明显的是，有一小部分谜题非常讨厌，并且会导致大多数简单求解器的运行时间爆炸。其中大部分是设计糟糕的谜题，人类也很难或不可能解决，但有些特别聪明的谜题，经验丰富的人类解决者可以轻松解决，使用比大多数人工智能程序可以管理的更深入的洞察力。

我自己编写了一个求解器，可以非常快速地解决大多数难题，并且我对许多其他求解器进行了调查，并通过基准结果比较了它们的性能。我还讨论了一类有趣的难题（多米诺难题），它展示了一些对聪明人不难的难题如何证明对大多数程序来说非常困难。我的求解器和多米诺拼图的链接将在调查中找到。

我认为仍有很大的改进空间，并会鼓励有新想法的人尝试一下。但值得注意的是，明显的事情已经做了，再做也没多大用处。

于 2010-10-08T15:21:28.243 回答
6

确定 Nonogram 解是否存在/是否唯一是 NP-hard。见http://en.wikipedia.org/wiki/Nonogram#cite_note-0

于 2009-05-01T23:04:18.350 回答
4

如果您尝试从“最受限制”的行或列中获取信息，它可能会大大减少您的搜索，而不是尝试放置“第一”行，这可能有几个强制值。一个快速的指示是将行/列中的所有值相加并添加 #_of_values - 1，然后查找具有最大此类值的行/列（或此值与行或列数之间的最小差异，如果行和列不同）。因此，如果您有一个 25x25 的拼图，并且其中一行是“5 1 1 6 1 1 3”，则该行的值为 24，这意味着它非常受限制 - 除了一个空白方块之外的所有相对位置在该行中是已知的，并且最后一个空白方块可以位于 8 个不同的相对位置中的任何一个。所以对于每一组实心方块，只有两种可能：额外的空白方块在该组的左侧，或者额外的空白方块在该组的右侧。因此，例如，该组 6 中的五个填充方块是已知的。

一旦您从一个方向获得了一些强制值，就会进一步限制与已知信息相交的另一个方向的任何组。因此，最好的方法可能是随着更多信息的了解，在列和行之间来回工作，这几乎是您需要手动解决它的方式。

于 2009-05-02T01:11:32.193 回答
3

真正的问题是，是否有人能想出比人类更快地解决上述难题的算法？这对于相对简单的谜题（例如参考谜题）来说很容易，但如果谜题变大，这里的大多数算法都会很快变慢。这是我试图解决的难题。问题是，例如，我相信第 4 行有 2220075 种可能的组合。如果 Charlie 的算法暂时接受了第 3 行的错误行，它将遍历第 4 行的所有这些组合。更不用说算法在第 35 行因为它在第 2 行犯的错误而自相矛盾的情况。

我的算法与约翰的相似。它无法在我的 64 位桌面上以 x86 模式运行。当我将它切换到 64 位模式并让它运行一夜之间时，我的电脑在早上完全无法使用。该过程保留了 8 Gigs 的内存（桌面上的 8 Gigs 物理内存），并且由于疯狂的交换，计算机不会响应。它甚至没有解决所有可能的行。更不用说它甚至没有触及可能的列组合。

List<List<int>> rows =
                new List<List<int>>()
                {
                    new List<int> { 8,29,4 },
                    new List<int> { 6,4,25,4,3 },
                    new List<int> { 5,3,2,3,9,4,2,1,3 },
                    new List<int> { 4,2,2,2,2,1,2,2 },
                    new List<int> { 4,1,1,9,10,2,2,1 },
                    new List<int> { 3,2,6,5,5,1,1 },
                    new List<int> { 3,1,5,5,1,1 },
                    new List<int> { 3,1,4,4,1,1 },
                    new List<int> { 3,1,4,4,1,1 },
                    new List<int> { 3,1,3,3,1,1 },
                    new List<int> { 3,1,3,6,2 },
                    new List<int> { 3,1,2,3,2,4,2 },
                    new List<int> { 4,3,1,8,7,1,2,3 },
                    new List<int> { 4,2,1,12,11,1,2,4 },
                    new List<int> { 5,1,2,7,2,2,6,1,1,4 },
                    new List<int> { 4,1,1,1,6,2,2,6,1,2,1,3 },
                    new List<int> { 4,1,1,2,4,3,4,3,1,1,1,1,3 },
                    new List<int> { 4,1,1,2,1,4,1,2,3,2,1,2,2 },
                    new List<int> { 3,1,1,1,2,5,6,1,1,1,3,2 },
                    new List<int> { 3,2,1,1,2,1,5,4,4,2,1,2,1,2 },
                    new List<int> { 3,2,2,1,1,4,2,2,3,1,1,2,1,1,2 },
                    new List<int> { 3,1,3,2,1,1,4,1,5,3,2,1,3,1,2 },
                    new List<int> { 3,1,2,1,2,1,3,7,4,1,4,2,2 },
                    new List<int> { 2,1,4,1,1,1,2,6,2,2,2,3,2,1 },
                    new List<int> { 2,2,4,1,2,1,2,5,2,1,1,3,2,1 },
                    new List<int> { 2,2,1,4,1,1,3,3,2,1,4,4,1 },
                    new List<int> { 2,3,3,2,1,3,3,7,4,1 },
                    new List<int> { 2,3,2,4,5,8,1,2,1 },
                    new List<int> { 1,1,3,11,6,7,1,3,1 },
                    new List<int> { 1,1,2,2,13,10,2,3,2 },
                    new List<int> { 1,2,3,1,6,1,1,7,1,5,2 },
                    new List<int> { 1,1,3,2,6,1,1,1,1,4,1,4,2 },
                    new List<int> { 1,1,6,7,2,4,2,5,6,1 },
                    new List<int> { 1,1,2,3,1,4,2,2,11,2,1 },
                    new List<int> { 1,1,1,1,2,1,5,10,1,1,1 },
                    new List<int> { 1,1,1,1,4,7,4,10,1,1,1 },
                    new List<int> { 1,2,1,1,28,1,1,3 },
                    new List<int> { 1,2,1,2,27,2,1,3 },
                    new List<int> { 1,1,1,1,26,1,1,1,1 },
                    new List<int> { 2,3,1,28,2,1,2,1 }
                };
            List<List<int>> cols =
                new List<List<int>>()
                {
                    new List<int> { 40 },
                    new List<int> { 28,1 },
                    new List<int> { 23,8 },
                    new List<int> { 5,6,7,4 },
                    new List<int> { 3,6,1,9,3,1 },
                    new List<int> { 2,3,2,5,4,2,2 },
                    new List<int> { 1,2,4,1,2,5,2 },
                    new List<int> { 1,1,4,9,2,3,2 },
                    new List<int> { 2,4,2,6,1,4,3 },
                    new List<int> { 1,4,1,3,4,1,6 },
                    new List<int> { 1,4,3,2,3,5,5 },
                    new List<int> { 2,4,1,2,3,4,1,3 },
                    new List<int> { 1,2,3,4,2,2,4,4,1 },
                    new List<int> { 1,1,2,3,2,1,4,2,4 },
                    new List<int> { 2,3,5,3,3,5,4 },
                    new List<int> { 3,1,6,1,2,5,5 },
                    new List<int> { 3,2,6,2,15 },
                    new List<int> { 3,1,8,2,13 },
                    new List<int> { 2,2,4,5,15 },
                    new List<int> { 2,2,2,2,22 },
                    new List<int> { 2,1,1,1,12,6 },
                    new List<int> { 2,1,10,4,5 },
                    new List<int> { 3,1,3,1,2,4 },
                    new List<int> { 3,1,1,4,3,1,4 },
                    new List<int> { 3,2,2,3,2,2,5 },
                    new List<int> { 3,1,1,5,1,1,5 },
                    new List<int> { 3,1,1,5,1,1,5 },
                    new List<int> { 3,1,1,5,1,1,5 },
                    new List<int> { 3,2,5,2,1,1,4 },
                    new List<int> { 3,1,1,3,2,2,4 },
                    new List<int> { 3,1,6,4,5 },
                    new List<int> { 2,2,12,2,6 },
                    new List<int> { 2,2,1,1,22 },
                    new List<int> { 2,1,2,2,5,15 },
                    new List<int> { 3,1,4,3,2,14 },
                    new List<int> { 3,1,7,2,1,13 },
                    new List<int> { 3,2,6,1,1,6,8 },
                    new List<int> { 3,2,5,2,2,4,7 },
                    new List<int> { 2,1,2,4,1,1,1,4,1,4,2 },
                    new List<int> { 1,1,4,4,3,1,4,5,1 },
                    new List<int> { 1,1,5,1,1,2,1,2,2,3,2 },
                    new List<int> { 1,5,2,2,1,5,5,3 },
                    new List<int> { 1,6,2,1,4,2,6,1 },
                    new List<int> { 1,6,2,6,5,2 },
                    new List<int> { 1,5,3,1,9,2 },
                    new List<int> { 2,2,4,2,6,3 },
                    new List<int> { 1,2,2,2,9,2,1 },
                    new List<int> { 3,5,5,8,4 },
                    new List<int> { 4,13,9 },
                    new List<int> { 27,2 }
                };

版权归 Tampere Guild of Information Technology / Kaisapais / 一家芬兰啤酒厂所有。

于 2009-05-02T08:58:56.453 回答
2

这似乎是带有回溯的深度优先搜索的一个非常明显的例子，就像“n 个皇后”问题一样。可爱的部分是除了放置行/列之外，您还可以移动块。

好的，这是一个大纲。

  1. 从一个空板开始，放置第一行

  2. 现在，使用该板，放置第二行，对照列约束检查它。如果通过，则针对该状态递归地尝试下一行；如果没有通过，则尝试该行的下一个可能位置。

  3. 如果在任何时候你用完了满足约束的行的可能放置，那么这个谜题就没有解决方案。否则，当您的行数用完时，您就解决了问题。

这些行可以被视为二进制数很方便，因此对可能性有自然的排序。

于 2009-05-01T22:27:26.427 回答
1

我现在没有足够的时间来充实解决方案，但这就是我要解决的方法。

“function1”在给定顶部或侧面数字的约束条件下确定行或列的可能组合，以及已填充的正方形和已清空的正方形。

“function2”从 function1 获取输出，并在逻辑上将所有结果放在一起 - 可以填充带有 1 的点。

“function3”从 function1 获取输出，并在逻辑上或所有结果一起 - 可以清空带有零的点。

继续将 function2 和 function3 应用于所有行和列，直到没有更多的框被清空或填充。如果谜题解决了，那么你就完成了。

如果这个谜题没有解决，那么取一个可能性最少的行或列，并应用第一个可能性。然后将 function2 和 function3 应用到新板上。如果它导致矛盾（行或列的可能性为 0），则取消应用该可能性并尝试不同的可能性。像这样继续递归，直到找到解决方案。

于 2009-05-01T22:04:19.943 回答
1

几个月前，我在 C++ 上编写了一个非图求解器。它只是寻找阴影和空白单元格的所有允许位置。在每个解决方案步骤中，它都会查看每个位置是否正常。因此，这里是 Chad Birch 的时序非图的结果：http: //i.stack.imgur.com/aW95s.png。

我也为 Mikko Rantanen 的 nongram 尝试了我的求解器：http: //i.stack.imgur.com/o1J6I.png。

于 2014-07-26T18:24:47.513 回答
0

Steven Simpson编写了一个非图求解器，可在不同版本中免费使用，包括 JavaScript 脚本。他在该网站上讨论了算法的细节（例如这里- 基本上，他使用了一系列在速度与完整性之间进行权衡的线解算器，再加上通过猜测所有线解算器何时到达死胡同来分而治之。他也有链接其他方法，它们覆盖的范围比我们这里更多。

于 2011-07-02T22:37:32.890 回答
0

让我指出经典非图谜题的 2 个有趣的转折点：

算法设计者面临的一个特殊挑战是彩色非图从同时考虑水平/垂直约束中受益匪浅。通常的逐行求解器在这里明显处于劣势。

于 2016-01-04T11:32:29.390 回答
0

这是我发现的：

所有 NP Complete 问题都有相同的感觉。 解决剩下的 80% 的案例总是很容易的。例如，纳克分解成一条线。可以编写一个例程solve_one_line(old_state, line_definition, new_state)来更新关于单行的已知信息，然后继续迭代行和列。然后它在少数情况下失败了，所以你写了一些东西来解决这些情况中的 80%。然后你添加随机数并解决你曾经找到的每一个案例，但有可能构建一个最优的坏案例。

其他遵循这种模式的游戏还有MineSweeper和Soduku。

并行思考很难。例如，您可能会发现，solve_one_line如果在一行上运行，上面的例程不会影响另一行，如果在列上运行，则不会影响另一列。

现在你得到：

  all_until_completion(rows):
      solve_one_line(...)
  all_until_completion(cols):
      solve_one_line(...)

这使您可以运行 20 个内核（在 20x20 上），而无需数据锁定或任何东西。然后你考虑在显卡上运行，每个单元都有一个处理器。然后你会注意到已经过去了多少时间。

有一次我在看现代计算机科学教科书时觉得自己老了，其中O(n)表示法被O(n, p)表示法取代，因为没有人愿意为单个处理器评估算法。8 个皇后解决方案是一种出色的快速递归算法，具有快速失败、高效的内存使用，并且仅在一个处理器上运行。

问题是玩的好借口。磨出更多相同的东西会很无聊。查看您可能需要更多经验的技术列表：行为驱动测试；依赖注入；纯函数式编程；神经网络；遗传算法；快速、马虎和失控；GPGPU；光学字符识别；以实例为导向的学习；众包；等等。选择一个并尝试以某种方式使用它来解决问题。有时目标不是解决问题，而是在未知的领域徘徊。

贡献一些东西。* 这可以像一篇文章一样简单。更好的可能是数百纳克的存储库，以便其他人可以玩。 [让我知道是否存在存储库，否则我会创建一个]。 一旦你有一些你觉得很整洁的东西，就开始贡献。注意克林贡语： 也许今天是死的好日子；我说我们发货。

因此，为 NP 问题编写奇异的并行解决方案并分享它们。祝你有美好的一天！

于 2016-04-21T17:40:58.043 回答