Masyu Puzzle





Masyu Puzzle也叫Pearl Puzzle,是一个和数独有一定相似处的逻辑游戏,但远远没有数独有名,目前在维基百科上连中文解释都还没有。网上搜到中文名称有翻译为“串珠”和“黑白珠链”的,但是无论哪种翻译都不是足够的权威。解Masyu Puzzle很有意思也很有难度,一个20*20大小的就足够让大多数人动一番脑筋了。
Masyu Puzzle的规则并不复杂,给你一个矩形格子,里面打好了mxn的方格,每个格子里面可能有一个黑珠子,也可能有一个白珠子,也可能什么都没有。现在需要你画一条封闭的折线,折线不自交,经过每一个黑珠子和白珠子一次。经过黑珠子的时候必须转弯,并且在经过黑珠子前和经过后的一格内必须是走的直线。经过白珠子的时候必须不转弯,并且在经过白珠子前和经过后的一格内,必须至少有一个是转弯。看着很绕,先上图来看看实例。


这两个图是维基上面转过来的,右边一个图像是左边一个图像的答案。

先分析一下怎么来玩Masyu Puzzle,这里给一个可以玩的网站。
http://www.nikoli.com/swf/ms.swf?loadUrl=/nfp/ms-0001.nfp&lang=1
……
http://www.nikoli.com/swf/ms.swf?loadUrl=/nfp/ms-0010.nfp&lang=1
上面是十个Masyu Puzzle的游戏,当然我只写了两个网址,看规律就知道中间的八个网址是什么了,你懂的。操作方法也很简单,试试就知道了。这十个游戏基本上是难度递增的。
首先要分析几个小例子就会发现一些规律。

  • 如果一个黑色珠子挨着墙壁,或者和墙壁相距一个格子,那么一定有朝墙壁反方向的线经过黑珠子。特别的,如果黑珠子在角落,那么经过他的线必然超着棋盘内部的两个方向。
  • 如果一个白色珠子挨着墙壁,那么一定有一条线沿着墙壁平行的穿过白珠子。
  • 如果两个黑色珠子挨着,那么他们一定各自引出一条线远离对方。
  • 如果三个白色珠子在同一行挨着,那么他们一定各自有一条线纵向穿过他们。

类似的规律还有一些,稍微分析一下就可以得到这个经验。

下面我们考虑一下如果我们写一个人工智能的程序去解这个游戏应该怎么做。首先以上几个规律是应该让程序知道的。另外程序还应该随时记录每个格子可以连向哪个方向和不能连向哪个方向,这些都可能使程序能分析出必须要连的线。如果一系列严谨的逻辑都不能得到更多的信息,就只好进行搜索,这时候一个比较有意思的想法是把已经连好的这些折线段如何更简单的串成一个回路。这个任务非常像TSP,这基本上也就是求解Masyu Puzzle是NP难的原因。所以我的想法是近似的求解这个类似TSP的问题用于搜索时候的启发函数是比较不错的。当然连通性等问题也是必须要考虑进去的。

事实上,如果我们把每个格子是否连向某个方向都定义成一个布尔变量,也即格子(i,j)朝k方向连边的话,那么x_{ijk}为真,否则为假。这里k代表上下左右中的某一个。这样一个mxn大的棋盘的Masyu Puzzle应该可以完全等价的转换成一个有4xmxn个布尔变量的SAT问题,只是这里面的约束实在太多了,不仅包括黑珠子白珠子,还包括回路等。所以感觉约束应该会有指数多个的。显然求解一个20×20的Masyu Puzzle要比求解一个4x20x20个变量、指数个约束的SAT问题简单的多。所以反过来想,如果给你这样一个转换来的SAT问题,恐怕是很难很难看出他等价于求解Masyu Puzzle,我也一直不能想明白如何根据一个SAT问题来认清它实际的内部结构,如果能做到这一点,可能求解SAT会容易不少。

本文来自Dora Blog,题目为Masyu Puzzle,转载请注明出处。
如果你喜欢我的博客,请订阅本博客的RSS以更方便的阅读
欢迎关注我的新浪微博:http://weibo.com/diaorui1987