解决Nonograms（Picross）问题

Question

解决Nonograms（Picross）问题

algorithmpuzzle

27

周五下午，让我们来解决一个有趣的难题/算法问题。

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

Nonograms是一个网格，每行和每列都定义了数字序列。这些数字定义了该行/列的“填充”方块的块，但是块两侧的未填充区域没有定义。例如，如果您有一个看起来像这样的行：

_{(来源：steam-punk.net)}

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

_{(来源：steam-punk.net)}

_{(来源：steam-punk.net)}

等等。

“4 5”仅告诉您，在该行的某个地方，有4个连续块填充，然后是5个连续块填充。这将是唯一填入的块，并且它们之前/之后的空间量未定义。

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

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

但是，我总是想，编写一个程序来解决这个相当容易的游戏。我从未开始过，但也许这里的一些人会喜欢挑战。如果发布了相当数量的解决方案，我将在一个大难题上对它们进行基准测试，类似于Paolo Bergantino在他的Boggle问题中所做的那样。有关攻击难题的方法的非诺格拉姆维基百科页面上有相当多的信息，如果您想引用它。

这是TylerK's Picross难题＃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

- Chad Birch

2

我解决了两个70x70的难题，我不认为我会再想做这件事了。花了我几天时间。然后我决定创建一个程序来帮我解决这些问题，但当我要输出算法时，我发现这对于没有真正乐趣的工作来说有点太多了。毕竟，我为什么要让计算机来解决我的难题呢？ - Peter Perháč

哇，我很惊讶。昨天我实际上为这些编写了一个算法。它相当暴力。由于我的笔记本电脑内存不足，我还没有时间测试其性能。如果最终有效，我可能会稍后发布它。 - Mikko Rantanen

@MasterPeter：我曾经有一个兼职工作，是做拼图检查员。有了计算机程序来检查这些拼图，我的工作变得轻松多了！而且，我对这些拼图并不是很擅长。我经常犯错，然后半个小时后才意识到，此时拼图已经处于无法恢复的状态，只能放弃了。 - Luke Woodward

现在我已经测试了求解器，发现它没有处理任何更大的难题的机会。它评估所有合法的行，但即使这个集合非常大，也需要花费很长时间。 - Mikko Rantanen

需要澄清拼图的规则。在给定的示例中，4和5之间的空格已经被定义。它至少为1。你不能让4和5长度填充块相邻。 - Peter Recore

10个回答

6

确定一个彩绘解谜游戏是否存在唯一解是 NP 难问题。参见 http://en.wikipedia.org/wiki/Nonogram#cite_note-0。

- Dave

3

几乎可以确定，在每个问题实例上，不存在比暴力尝试所有可能性更快的算法。 - j_random_hacker

3

进一步翻译：如果你能想出一个算法，无论我向你提出什么问题实例，它总是比暴力搜索更好，那么你就比计算机科学领域的每个人都聪明。 - j_random_hacker

14

这些翻译并不十分准确。除非P=NP，否则在所有情况下都不会有一个多项式时间的算法，但你仍然可以比暴力搜索更好。例如，暴力求解旅行商问题的时间复杂度是O(n!)，但理论上可能存在一个O(2^n)甚至O(n^(ln n))的算法，即使P!=NP。为了比较，10!=3628800，2^10=1024，10^(ln 10)=200.7。这种改进对于中等规模的n值而言可以产生相当大的差异，尽管它们仍然是非多项式的。 - dewtell

3

同样地，正如维基百科页面所写，我们并不打算解决每一个可能的难题。假设我们在看商业谜题，我们只能限制于那些(1)有唯一解的非诺格矩阵，(2)其解应该能够被人类在合理时间内找到。这意味着，如果我们按正确顺序进行推理的话，路径上应该只涉及极少的分支。 - dewtell

4

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

一旦您从一个方向获得了一些强制值，就会进一步限制与已知信息相交的其他方向的任何组。因此，最好的方法可能是在更多信息变为已知时在列和行之间来回工作，这基本上是您需要手动解决问题的方式。

- dewtell

3

真正的问题是是否有人能够提出比人类更快地解决这个谜题的算法？对于相对较易的谜题，如参考谜题，这很容易，但如果谜题变得更难，这里的大多数算法将很快减速。这是我试图解决的谜题。问题在于第4行有2220075个可能的组合，我相信。如果查理的算法暂时接受了第3行的错误行，它将遍历所有这些第4行的组合。更不用说算法在第35行上因为它在第2行犯了一个错误而与自己发生矛盾的情况了。

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

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信息技术协会/Kaisapais/芬兰啤酒厂所有。

- Mikko Rantanen

2

如果程序遵循我的建议，从最受限制的行或列开始，它将从第一列开始，这将锁定每行的第一组，并立即为您提供大部分前几列。即使有太多的可能性无法放置每个组，能够推断出一行或一列的一部分也是有帮助的。 - dewtell

2

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

好的，这是一个大纲：

1. 从一个空棋盘开始，放置第一行。 2. 现在，使用该棋盘，放置第二行，并检查它是否符合列约束条件。如果通过，请递归地尝试下一行状态；如果未通过，则尝试该行的下一个可能位置。 3. 如果您在任何时候用完满足约束条件的行的所有可能位置，则谜题无解。否则，当您用完所有行时，您已经解决了问题。

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

- Charlie Martin

这正是我心中考虑着自己去实现它的解决方案，如果有机会，我可能会尝试在这个周末把它编码出来。 - Chad Birch

有趣的方法。在我看来，这可能会导致许多深度搜索空间的评估失败，因为浅层搜索深度上一行的错误放置。换句话说，第二行的无效放置只能通过搜索到棋盘上更晚的行来证明。正如维基百科页面所描述的那样，有许多方法可以使用，而不需要模拟-它们可以提取关于棋盘的确定可知信息。 - Niall Connaughton

1

这是我找到的：

所有NP完全问题都有相同的感觉。总是很容易解决剩余情况的下一个80％。例如，nanogram可以分解为单行。您可以编写一个例程solve_one_line(old_state, line_definition, new_state)来更新单行的已知信息，然后在行和列上不断迭代。然后它会失败几次，因此您需要编写一些内容来解决其中80％的情况。然后添加随机数字并解决您曾经发现的每个案例，但可能构造出最优糟糕的情况。

其他遵循此模式的游戏包括扫雷和数独。

并行思考很难。例如，您可能会发现上述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；OCR；基于示例的学习；众包等。选择其中一个并尝试使用它来解决问题。有时目标不是解决问题，而是漫步在未知的领域中。 做出一些贡献。 这可以是一个简单的写作。更好的可能是一个包含数百个纳米克的存储库，以便其他人可以玩耍。[如果存在存储库，请告诉我，否则我会创建一个]。一旦你有了一些你觉得很不错的东西，就开始做出贡献。记住克林贡话：也许今天是死的好日子；我说我们把它运送出去。

因此，编写奇怪的、并行的 NP 问题解决方案并分享它们。祝你拥有愉快的一天！

- Charles Merriam

仓库实际上存在：http://webpbn.com/。请查看如何在您的代码中访问这些谜题 https://github.com/tsionyx/pynogram/blob/77335fe/pynogram/reader.py#L152 - tsionyx

1

几个月前，我在C++上编写了一个非词谜的解算器。它只查找阴影和空格单元的所有可接受位置。在每一步解决方案时，它都会检查每个位置是否正确。以下是Chad Birch的非词谜解结果及其计时：http://i.stack.imgur.com/aW95s.png。我还尝试了Mikko Rantanen的非词谜解算器：http://i.stack.imgur.com/o1J6I.png。

- klimenkov

1

我现在没有足够的时间来完善一个解决方案，但这是我解决它的方法。

“function1”确定一行或一列可能的组合，考虑顶部或侧面数字的限制，以及已经填充和清空的方格。

“function2”获取从function1得出的输出，并对所有结果进行逻辑与运算 - 带有1的位置可以填充。

“function3”获取从function1得出的输出，并对所有结果进行逻辑或运算 - 带有0的位置可以清空。

将function2和function3应用于所有行和列，直到没有更多的方框被清空或填充。如果拼图已经解决了，那么你完成了。

如果拼图未解决，则选择具有最少可能性的行或列并应用第一种可能性。然后将function2和function3应用于新板。如果导致矛盾（一行或一列的可能性为0），则取消应用该可能性并尝试其他可能性。像这样继续递归，直到找到解决方案。

- John

2

如果您有一个50x50的谜题并且其中一行中的数字为1 1 1 1 1 1 1 1 1 1 1 1，那么这个解决方案将无法继续。这里有数百万种可能的组合。 - Luke Woodward

正如Dewtell所说，如果您尝试在解决方案的早期评估特定行，则该方法只是一种糟糕的方法。如果求解器可以在评估这样一行之前填写大部分谜题，则搜索空间可以从数百万个减少到十个或更少。想象一下，如果手动解决，您将如何攻击这样一行-您会最后完成它。 - Niall Connaughton

0

Steven Simpson编写了一个免费提供不同版本的非诺格谜题求解器，其中包括JavaScript脚本。他在网站上讨论了算法的细节（例如这里），基本上，他使用一系列线性求解器来权衡速度和完整性，并通过猜测进行分治，当所有线性求解器都陷入死局时。他还提供了其他方法的链接，这些方法涵盖了比我们在此处介绍的更多领域。

- dewtell

0

让我提出两个经典的非诺格拉姆谜题中有趣的变化：

当谜题不仅列出了占用单元格的长度，而是做了更多操作。公共挑战提前限制了某些单元格被占用： http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx
当非诺格拉姆不仅包含空/占用单元格，而且使用不同颜色的块来占用单元格。例如请参见 http://onlinenonograms.com ;从手动求解这些问题中，我感到这些实际上比常规的非诺格拉姆更容易解决。

对于算法设计者来说，一个特殊的挑战是彩色非诺格拉姆在考虑水平/垂直约束时受益匪浅。通常的逐行求解器在这里明显处于劣势。

- user1564286

GCHQ谜题提前提供了一些填充的单元格，以确保谜题只有一个解。由于谜题的结果是一张图像，可以引导您进入下一个谜题，如果有多个解，则人们可能会解决谜题，但仍然没有“正确”的答案。如果您考虑如何生成这样的谜题，您将得到解决方案图片，生成匹配的线索，然后计算这些线索是否可以导致多个解决方案。如果是这样，您必须填写仅在所需解决方案中填写的单元格-填写的单元格越多，谜题就越容易。 - Niall Connaughton

1

如果您尝试在没有填充单元格的情况下解决GCHQ难题，那么可能会有几种不同的解决方案。最终，您将达到一个状态，在该状态下必须尝试填充某个特定的单元格以查看是否会产生矛盾。有几种不同的方法可以填充单元格，仍然能够得出完整的解决方案。 - Niall Connaughton

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jan Wolter · Accepted Answer

是的，这个问题是NP完全问题，但这意味着随着谜题的规模增长，您几乎无法避免指数级别的运行时间增长。但在现实生活中，谜题的大小并不会增长。几乎没有人会费力地制作超过100x100的谜题，绝大部分谜题的大小都小于50x50。建立一个能够在几秒钟内解决书籍和杂志上发布的95％谜题的求解器实际上并不特别具有挑战性。一个相当简单的深度优先搜索系统就能做到。

不太明显的是，有一小部分谜题非常棘手，对于大多数简单的求解器而言会导致运行时间激增。其中大部分是糟糕设计的谜题，对于人类来说也难以或不可能解决，但有些特别巧妙的谜题经验丰富的人类解谜者可以轻松解决，使用比大多数AI程序更深刻的洞见。

我编写了自己的求解器，可以很快地解决大多数谜题，并进行了许多其他求解器的调查，比较了它们的性能。我还讨论了一个有趣的难题类别（多米诺谜题），展示了一些对于聪明人来说不难但对于大多数程序很难的谜题。在调查中，将找到链接到我的求解器和多米诺谜题。

我认为仍有很大的改进空间，并鼓励有新想法的人尝试一下。但值得注意的是，显而易见的事情已经做完了，没有太多重复的用处。