解决非图表（Picross）

问题描述 投票：25回答：10

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

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

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

（来源：steam-punk.net）

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

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

等等

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

当所有行和列符合其定义时，拼图就完成了，没有任何矛盾。

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

但是，我总是想到编写一个程序来解决它是一个非常简单的游戏。我从未接触过它，但也许这里的一些人会喜欢这个挑战。如果发布了相当数量的解决方案，我会将它们基于一个大型拼图相互比较，类似于Paolo Bergantino did here with his Boggle question。关于攻击谜题的方法，有很多关于Nonogram Wikipedia page的信息，如果你想引用它的话。

这是TylerK的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
algorithm puzzle
10个回答
21
投票

是的，这个问题是NP完全的，但这只意味着随着拼图大小的增加你（几乎）陷入指数增长的运行时间。但在现实生活中，拼图尺寸不会增长。几乎没有人愿意制造大于100x100的谜题，绝大多数都小于50x50。构建一个能够在几秒钟内解决95％的书籍和杂志中谜题的解算器实际上并不是特别具有挑战性。一个相当直接的深度优先搜索系统将做到这一点。

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

我写了一个我自己的解算器，可以很快解决大多数难题，而且我做了一个survey of many other solvers，基准测试结果比较了他们的表现。我还讨论了一个有趣的难题类（多米诺拼图），它演示了一些对于一个聪明的人来说难以为大多数程序所用的难题。调查中将找到我的求解器和Domino Puzzle的链接。

我认为仍有很大的改进空间，并鼓励有新想法的人开始考虑。但值得注意的是，显而易见的事情已经完成，并且再次做这些事情的用处不大。

0
投票

这是我发现的：

所有NP完全问题都有相同的感觉。解决接下来80％的剩余案例总是很容易的。例如，纳克分解成单行。可以编写一个例程，http://onlinenonograms.com来更新已知的单行，然后继续迭代行和列。然后它在几个案例中失败了，所以你写了一些东西来解决80％的案例。然后你添加随机数并解决你遇到过的每一个案例，但是可以构造一个最佳的错误。

遵循此模式的其他游戏是MineSweeper和Sudoku。

并行思考很难。例如，如果在列上运行，如果在行或其他列上运行，则可能会发现上面的solve_one_line(old_state, line_definition, new_state)例程不会影响另一行。

现在你得到：

solve_one_line

这使您可以在没有数据锁定或其他任何情况下运行20个内核（20x20）。然后你考虑在每个单元处理器的图形卡上运行。然后你会注意到已经过了多少时间。

有一次我感觉自己老了，正在看现代计算机科学教科书，其中O（n）符号被O（n，p）符号替换，因为没有人会关心评估单个处理器的算法。 8皇后解决方案是一种优秀的快速递归算法，具有快速失败，高效的内存使用，并且只能在一个处理器上运行。

问题是很好的借口。磨出更多相同的东西变得无聊。查看可能需要更多经验的技术列表：行为驱动的测试;依赖注入;纯函数式编程;神经网络;遗传算法;快速，草率和失控; GPGPU; OCR;示例驱动的学习;众包;选择一个并尝试以某种方式使用它来解决问题。有时，目标不是解决问题，而是漫游未知领域。

贡献一些东西。*这可以是一个简单的写作。更好的可能是数百纳克的存储库，所以其他人可以玩。 [如果存在存储库，请告诉我，否则我会制作存储库]。一旦你找到一些整洁的东西就开始做出贡献。注意克林贡语：或许今天是美好的一天;我说我们发货了。

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

6
投票

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

4
投票

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

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

2
投票

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

好的，这是一个大纲。

  1. 从空板开始，放置第一行
  2. 现在，使用该板，放置第二行，根据列约束检查它。如果它通过，递归地尝试针对该状态的下一行;如果它没有通过，那么尝试该行的下一个可能的位置。
  3. 如果您在任何时候用尽了满足约束的行的可能位置，那么拼图就没有解决方案。否则，当你用完大麻时，你就解决了这个问题。

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

2
投票

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

我的算法类似于约翰的算法。它无法在我的64位桌面上以x86模式运行。当我将其切换到64位模式并让它在一夜之间运行时，我的电脑在早上完全无法使用。这个过程保留了8 Gig的内存（桌面上有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 }
                };

版权归信息技术的坦佩雷公会/ Kaisapais /芬兰啤酒厂所有。

1
投票

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

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

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

“function3”将function1的输出与逻辑或所有结果一起取出 - 带零的点可以清空。

继续将function2和function3应用于所有行和列，直到不再清空或填充框。如果解决了这个难题，那么就完成了。

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

1
投票

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

我也尝试了我的解算器Mikko Rantanen nonogram：qazxsw poi。

0
投票

http://i.stack.imgur.com/o1J6I.png编写了一个非图解算器，可以在不同版本中免费获得，包括JavaScript脚本。他在该网站上讨论了算法的细节（例如Steven Simpson-基本上，他使用了一系列线条，它们在速度与完整性之间进行权衡，并通过猜测所有线条到达死胡同时加入分而治之。他还有链接其他方法比我们在这里有更多的基础。

0
投票

让我指出经典的非图形拼图上有两个有趣的曲折：

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

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.