嘿,这是星期五下午,让我们有一个有趣的拼图/算法问题来解决.
我最喜欢的任天堂DS游戏之一是Picross DS.游戏很简单,它涉及解决称为Nonograms的谜题.您可以在这里尝试一个简单的在线Picross克隆:TylerK的Picross.
非图是网格,为网格的每一行和每列定义数字序列.这些数字定义了该行/列的"填充"方块的块,但未定义块两侧的未填充区域.例如,如果您有一行如下所示:
http://steam-punk.net/images/picross1.jpg
该行的可能解决方案包括:
http://steam-punk.net/images/picross2.jpg http://steam-punk.net/images/picross3.jpg
等等
"4 5"只是告诉你,在行的某个地方,填充了4个连续的块,然后填充了5个连续的块.这些块将是填充的唯一块,并且它们之前/之后的空间量是没有定义的.
当所有行和列符合其定义时,拼图就完成了,没有任何矛盾.
概念上非常简单的游戏,但手动解决其中一些可能需要一段时间.Picross DS的谜题逐渐增加到25x20网格,这通常需要我花半个小时来解决.
但是,我总是想到编写一个程序来解决它是一个非常简单的游戏.我从未接触过它,但也许这里的一些人会喜欢这个挑战.如果发布了相当数量的解决方案,我会将它们作为一个大型拼图相互比较,类似于Paolo Bergantino在这里用他的Boggle问题做的.如果你想参考,那么在Nonogram Wikipedia页面上有很多关于攻击谜题的方法的信息.
这是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
小智 21
是的,这个问题是NP完全的,但这只意味着随着拼图大小的增加你(几乎)陷入指数增长的运行时间.但在现实生活中,拼图尺寸不会增长.几乎没有人愿意制造大于100x100的谜题,绝大多数都小于50x50.构建一个能够在几秒钟内解决95%的书籍和杂志中谜题的解算器实际上并不是特别具有挑战性.一个相当直接的深度优先搜索系统将做到这一点.
不太明显的是,有一小部分谜题非常讨厌,并且会导致大多数简单求解器的运行时间爆炸.其中大多数都是设计糟糕的谜题,这些谜题对于人类来说也很难或不可能解决,但有些谜题是人类解算者可以轻松解决的特别聪明的谜题,使用比大多数AI程序可以管理的更深入的见解.
我写了一个我自己的求解器,可以很快解决大多数谜题,并且我已经对许多其他求解器进行了调查,并对基准测试结果进行了比较.我还讨论了一个有趣的难题类(多米诺拼图),它演示了一些对于一个聪明的人来说难以为大多数程序所用的难题.调查中将找到我的求解器和Domino Puzzle的链接.
我认为仍有很大的改进空间,并鼓励有新想法的人开始考虑.但值得注意的是,显而易见的事情已经完成,并且再次做这些事情的用处不大.
确定Nonogram解决方案是否存在/是唯一的是NP难的.见http://en.wikipedia.org/wiki/Nonogram#cite_note-0
我现在没有足够的时间来充实解决方案，但这就是我解决这个问题的方法。
“function1”在给定顶部或侧面的数字以及已填满和已清空的方格的约束的情况下确定行或列的可能组合。
“function2”获取 function1 的输出，并逻辑地将所有结果放在一起 - 带 1 的位置可以填写。
“function3”获取 function1 的输出并逻辑地或将所有结果放在一起 - 带零的点可以被清空。
继续将函数 2 和函数 3 应用于所有行和列，直到没有更多的框被清空或填充。如果谜题解决了，那么你就完成了。
如果谜题没有解决，则取可能性最少的行或列并应用第一个可能性。然后将function2和function3应用到新板上。如果它导致矛盾（行或列的可能性为 0），则取消应用该可能性并尝试不同的可能性。如此不断递归，直到找到解。