algorithm - 解决 Nonograms (Picross)

Question

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

我最喜欢的 Nintendo DS 游戏之一是 Picross DS .游戏非常简单，它涉及解决名为 Nonograms 的谜题。 .您可以在这里尝试一个简单的在线 Picross 克隆:TylerK's Picross .

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

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

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

<sub>(来源:steam-punk.net)

(来源:steam-punk.net)</sub>

等等

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

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

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

但是，我总是想到，编写一个程序来解决这将是一个非常容易的游戏。我从来没有抽出时间来解决这个问题，但也许这里的一些人会喜欢这种挑战。如果发布了相当数量的解决方案，我将在一个大难题上对它们进行基准测试，类似于 Paolo Bergantino did here with his Boggle question。 . Nonogram Wikipedia page 上有很多信息关于解决难题的方法，如果您想引用的话。

这是来自 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

Answer 1

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

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

我自己写了一个求解器，可以非常快速地解决大多数难题，而且我已经完成了 survey of many other solvers与基准测试结果比较它们的性能。我还讨论了一类有趣的难题(多米诺骨牌难题)，它展示了一些对于聪明人来说并不难的难题对大多数程序来说是非常困难的。将在调查中找到指向我的求解器和多米诺拼图的链接。

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