今天是星期五下午，让我们解决一个有趣的难题/算法问题。
我最喜欢的Nintendo 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
最佳答案
是的，问题是NP完全的，但这仅意味着(随着拼图的大小的增加)您(相当多地)陷入了呈指数增长的运行时间。但是在现实生活中，拼图的大小不会增长。几乎没有人会费心去制作大于100x100的拼图，而绝大多数拼图都小于50x50。实际上，构建一个求解器可以在几分之一秒内解决95％的书籍和杂志上发布的难题，这并不是特别困难。一个相当简单的深度优先搜索系统将做到这一点。
不太明显的是，有一小部分难题非常讨厌，并且会导致大多数简单的求解器的运行时爆炸。其中大多数都是设计不好的难题，人类也很难或不可能解决，但其中一些难题特别聪明，有经验的人类求解者可以使用比大多数AI程序所能管理的更深刻的见解轻松解决。
我已经编写了自己的求解器，可以非常快地解决大多数难题，并且我完成了survey of many other solvers并将其性能与基准测试结果进行比较。我还将讨论一类有趣的硬难题(多米诺骨牌难题)，该难题演示了对于某些聪明人来说并不难的一些难题如何在大多数程序中都很难解决。在调查中将找到指向我的求解器和Domino拼图的链接。
我认为仍有很大的改进空间，并鼓励有新想法的人尝试一下。但是，值得注意的是，显而易见的事情已经完成，并且再做一次没有多大用处。
关于algorithm - 解非图(Picross)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/813366/