今天是星期五下午，让我们来解决一个有趣的谜题/算法问题。
我最喜欢的任天堂 DS 游戏之一是绘图方块 DS http://en.wikipedia.org/wiki/Picross_Ds。游戏非常简单，它涉及解决称为连线图 http://en.wikipedia.org/wiki/Nonogram。您可以在这里尝试一个简单的在线 Picross 克隆：TylerK 的绘图方块 http://www.thetimmys.com/flash/picross/.
Nonograms 是一个网格，其中为网格的每一行和每一列定义了数字序列。这些数字定义了该行/列的“填充”方块块，但块两侧的未填充区域未定义。例如，如果您有一行如下所示：
(source: steam-punk.net http://steam-punk.net/images/picross1.jpg)
该行的可能解决方案包括：
(source: steam-punk.net http://steam-punk.net/images/picross2.jpg)
(source: steam-punk.net http://steam-punk.net/images/picross3.jpg)
etc.
“4 5”只是告诉您，在行中的某个位置，有 4 个连续的块被填充，然后是 5 个连续的块被填充。这些将是唯一被填充的块，并且它们之前/之后的空间量是没有定义的。
当所有行和列都满足其定义且没有任何矛盾时，拼图就完成了。
概念上非常简单的游戏，但手动解决其中一些问题可能需要相当长的时间。 Picross DS 的谜题逐渐增大到 25x20 网格，这通常需要我大约半个小时才能解决。
然而，我总是想到，编写一个程序来解决这个游戏是相当容易的。我从来没有抽出时间来做这件事，但也许这里的一些人会喜欢这个挑战。如果发布了相当数量的解决方案，我将在一个大的谜题上对它们进行基准测试，类似于保罗·贝甘蒂诺 (Paolo Bergantino) 在这里提出了他的令人困惑的问题 https://stackoverflow.com/questions/746082/how-to-find-list-of-possible-words-from-a-letter-matrix-boggle-solver。里面有相当多的信息Nonogram 维基百科页面 http://en.wikipedia.org/wiki/Nonogram#Solution_techniques关于解决谜题的方法，如果你想参考的话。
这是来自 TylerK's 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
是的，这个问题是 NP 完全的，但这仅仅意味着随着谜题规模的增大，你（几乎）会陷入指数增长的运行时间。但在现实生活中，拼图的大小不会增加。几乎没有人愿意构建大于 100x100 的谜题，绝大多数都小于 50x50。构建一个能够在几分之一秒内解决书籍和杂志上发布的 95% 谜题的解算器实际上并不是特别具有挑战性。一个相当简单的深度优先搜索系统就可以做到这一点。
不太明显的是，有一小部分谜题非常棘手，会导致大多数简单求解器的运行时间爆炸。其中大多数都是设计糟糕的谜题，人类也很难或不可能解决，但有些是特别聪明的谜题，经验丰富的人类解谜者可以轻松解决，使用比大多数人工智能程序更深入的洞察力。
我自己编写了一个求解器，可以非常快速地解决大多数谜题，并且我已经做了一个对许多其他求解器的调查 http://webpbn.com/survey/与基准结果比较它们的性能。我还讨论了一类有趣的难题（多米诺难题），它演示了一些对于聪明人来说并不困难的难题对于大多数程序来说却非常困难。调查中可以找到我的求解器和多米诺拼图的链接。
我认为还有很大的改进空间，并会鼓励有新想法的人尝试一下。但值得注意的是，显而易见的事情已经做了，再做也没有多大用处。