求解非程序(picross)

是的,这个问题是np完全的,但这只意味着你(几乎)被困在随着谜题大小的增长而呈指数增长的运行时间中。但在现实生活中,拼图的尺寸并没有增长。几乎没有人会费心制作大于100x100的拼图,而绝大多数都小于50x50。建立一个能够在几秒钟内解决95%的图书和杂志上的难题的解算器,实际上并不是特别具有挑战性。一个相当直截了当的深度优先搜索系统可以做到这一点。

不太明显的是,有一小部分的谜题是相当恶劣的,将导致运行时间爆炸,为大多数简单的解决者。其中大多数是设计糟糕的谜题,人类也很难或不可能解决,但有些是特别聪明的谜题,经验丰富的人类解题者可以很容易地解决,使用比大多数人工智能程序更深刻的洞察力。

我已经写了一个自己的解决方案,将解决大多数难题非常快,我做了一个 survey of many other solvers 与基准测试结果进行比较。我还讨论了一类有趣的硬拼图(domino拼图),它演示了一些对聪明人来说并不难的拼图对大多数程序来说是多么的难。我的解算器和多米诺难题的链接将在调查中找到。

我认为还有很大的改进空间,可以鼓励有新想法的人尝试一下。但值得注意的是,显而易见的事情已经做了,再做也没有多大用处。

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

如果您试图从“最受约束”的行或列(可能有多个强制值)获取信息,而不是试图放置“第一”行,它将大大减少您的搜索。一个快速的指示是将行/列中的所有值相加,并添加u个值-1,然后查找此类值最大的行/列(如果行和列不同,则此值与行或列的之间的最小差异)。因此,如果你有一个25x25的谜题,其中一行是“5 1 1 1 6 1 1 3”,那么该行的值为24,这意味着它是非常有约束的——在该行中除了一个空白方块之外,所有的相对位置都是已知的,而最后的空白方格可以在8个不同的相对位置中的任何一个。所以对于每一组填充的正方形,只有两种可能:额外的空白正方形在这个组的左边,或者额外的空白正方形在这个组的右边。例如,这6个方格中有5个是已知的。

一旦从一个方向得到一些强制值,则会进一步约束与已知信息相交的另一个方向的任何组。因此,随着更多信息的出现,最好的方法可能是在列和行之间来回工作,这几乎是手工解决问题的方法。

对于深度优先的回溯搜索来说,这似乎是一个很明显的例子,就像“n皇后”问题一样。有趣的是,除了放置行/列之外,还可以移动块。

好的,这是一个提纲。

1. 从一块空木板开始,放第一排

2. 现在,使用这个板,放置第二行,对照列约束检查它。如果通过,则递归地针对该状态尝试下一行;如果不通过,则尝试该行的下一个可能位置。

3. 如果在任何时候,满足约束的行的可能位置都用完了,那么这个难题就没有解决方案。否则,当你用完罗恩斯,你就解决了问题。

这些行可以被当作二进制数来处理,这很方便,因此对可能性有一个自然的排序。

真正的问题是,是否有人能想出比人类更快地解决上述难题的算法?这对于相对简单的谜题来说是很容易的,例如参考谜题,但是如果谜题增长,这里的大多数算法将很快减慢速度。这是我试图解决的难题。问题是,例如第四行有2220075个可能的组合,我相信。如果charlie的算法暂时接受第3行的错误行,那么它将遍历第4行的所有这些组合。更不用说第35行的算法与第2行的错误自相矛盾了。

我的算法和约翰的相似。它在64位桌面上无法以x86模式运行。当我将它切换到64位模式并让它运行一整夜时,我的计算机在早上完全无法使用。这个过程保留了8千兆内存(桌面上有8千兆物理内存),由于疯狂的交换,计算机没有响应。它甚至没有解决所有可能的争吵。更不用说它甚至没有触及可能的列组合。

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 }
                };

版权归坦佩雷信息技术协会/凯萨帕斯/芬兰啤酒厂所有。

我现在没有足够的时间来完善解决方案,但这就是我要解决的方法。

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

“Function2”将Function1的输出和逻辑以及所有的结果放在一起—可以填入带一个的点。

“Function3”将Function1的输出和逻辑或所有结果放在一起-带零的点可以被清空。

继续将函数2和函数3应用于所有行和合谋,直到不再清空或填充框。如果谜题解决了,你就完了。

如果这个谜题没有解决,那么选取一行或一列可能性最小的行或列,并应用第一个可能性。然后将Function2和Function3应用于新板。如果它导致矛盾(行或列的可能性为0),则取消应用该可能性并尝试其他可能性。一直这样递归直到找到解决方案。

几个月前,我在C++上写了一张非图的解题器。它只是寻找阴影和空白单元格的所有允许位置。在每一个解决方案步骤上,看起来每个位置都正常。 这是Chad Birch关于时间的非程序的结果: http://i.stack.imgur.com/aW95s.png 是的。

我也为米科·兰塔宁的《非拉姆》尝试了我的解算器: http://i.stack.imgur.com/o1J6I.png 是的。

Steven Simpson 编写了一个非程序解算器,可以在不同版本中自由使用,包括一个javascript脚本。他在那个网站上讨论了算法的细节(比如 here -基本上,他使用了一系列折衷速度和完整性的线解算器,再加上通过猜测所有线解算器何时到达死胡同而分而治之。他还与其他方法有联系,这些方法比我们这里涉及的范围更广。

让我指出经典的非程序拼图有两个有趣的转折点:

• 当拼图不仅仅列出占用的单元格长度时。这一公开挑战提前限制了一些牢房被占用: http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx

• 当非程序包含的不仅仅是空的/已占用的单元格,而是使用不同颜色的块来占用单元格时。例如,请参见 http://onlinenonograms.com ;通过手工解决这些问题,我感觉这些问题实际上比常规的非程序更容易解决。

算法设计者面临的一个特殊挑战是,将水平/垂直约束考虑在一起,有色非程序将受益匪浅。通常的每行解算器在这里处于明显的劣势。

以下是我的发现:

所有np完全问题都有相同的感觉。 剩下的80%的案子总是很容易解决的。例如,纳米颗粒分解成一条线。一个人可以写一个程序, 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问题的解决方案并与大家分享。祝你今天愉快!