数回（SlitherLink）游戏的⾃动求解算法
数回是⼀个很有趣的智⼒⼩游戏，与数独游戏同属数字类的休闲⼩游戏，不过⽐数独要更轻松⼀点，更容易上⼿。前段时间我开始玩数回，在IOS和安卓上都有很多免费的数回⼩游戏，玩得不亦乐乎，不过后⾯难度⼤的玩起来就⼀点也不轻松了，需要进⾏⼤量的猜测，⽽这些软件都没有中途建⽴恢复点的功能，⼀旦猜错了想回退去往往忘了该回退到哪了，整个盘⾯⼀乱就完了。作为⼀个会编程的（连程序猿都算不上），就想⾃⼰编⼀个能建⽴标记点和和回滚功能的数回⼩游戏，于是开始学习python下的图形界⾯编程。可是很快想法就变了，何不⼲脆编个⾃动求解的程序？于是主要⽬标⼜从界⾯转向⾃动求解算法上去了 ，对界⾯的设计也就不怎么上⼼了，没有开发什么建⽴恢复点的功能（其实也不难，⽐算法简单，只是⼼思都到算法上去了，开发界⾯纯粹只是为了有⼀个展现和调试环境，见上⼀遍博客），于是就花了⼀个星期开发了⼀个最简界⾯，剩下的时间都花到算法的开发上去了。开始没想到时间会⽤得这么长，也幸好这个春节假期也是相当的长（鲁迅说过，⼈世间的悲欢并不相通。为那些没能看到庚⼦年的春天的不幸⼈们默哀，然⽽很快他们就不会再被提起，或许会有很多形式上的记念，然⽽从举办这些记念的⼈的⼼⾥，这些记念更多的是为了让⼈们忘却吧），终于在正式复⼯的最后⼀天，在各种想法的混乱决策和与各种bug⽃争了⼏天以后，完成了这个算法，可以⽤很不精炼的python代码（主要是各种想法中反反复复，留下了⼀些很不必要的东西）在⼏秒钟内求解各种数回软件上的最难等级的盘⾯，真是值得庆祝⼀下。
最终的代码其实并不长，才刚到千⾏，之所以⽤了这么长时间，是因为遍了⽹上，并没有到⼀点求解数回的算法的⽂章，只能⾃⼰开发。相⽐之下，数独等游戏的讨论就多得多，看来这个还有点冷门。从最基本的估算就知道，简单的深部优先搜索从时间复杂度上来看是⾏不通的，实际上我在完成这个算法后也尝试过⽤⼀下简单深度优秀搜索看看效果，结果是时间是不可接受的。那么要开发⼀个可接受的算法，先得对这个游戏的⼈⾁解题过程有些了解才⾏。
其实玩过数回的⼈都知道，玩数回只要记住两个要点基本上就差不多了，第⼀，数回是有⼀些定式的，⽐如最基本的两个3；第⼆，需要猜测时，从线头开始。
数回的定式不多，常⽤的基本上就是33，30这⼏个，
当然还有⼀些⽐较复杂的，但实际很少⽤到。如果将连线也考虑进去的话，定式会多⼀此，但那太难记了。这⼏个定式虽然少，但是可以为玩家提供⼀个突破⼝，从突破⼝开始，慢慢“蚕⾷”整个盘⾯，从⽽完成整个游戏。⽽蚕⾷的过程，很重要⼀点的技巧就是从线头处开始要简明⼀些，⽽不是去点那些没有任何线索的空⽩处。
另外，玩数回⼀个新⼿不怎么喜欢⽤到，⽽⽼⼿⼤多会⽤到的⽅法是，把确定不会连接的线标记出来，这样有助于分析盘⾯，更容易看出连接关系。⼀般游戏中会提供⼀个打叉的功能，⽐如像这样：
最后再强调⼀点，就是所有的线条最后要连成⼀个不交叉的单环，⽽不能是⼏个独⽴的⼩环。
好了，其实从玩法上要说就也就这么多了。不过怎么编程去实现，确实让我想了好⼀段时间。最后，我确定了⼀个定式匹配+深度优先遍历的算法。总的两说，就是
1.先遍历整个盘⾯，寻可以匹配的定式，将可以确定状态的连线的状态进⾏设置。这个状态包括必然有连接（把头连上）或者必然⽆连接（打个叉）。
2.在上⼀轮改变过状态的点附近进⾏定式匹配，确定可以确定的状态，反复进⾏本步骤，直到没有可以确定的状态。
3.选择⼀个线头，猜测⼀步连接，然后执⾏2的操作
反复递归执⾏2，3，如果遇到死局，则恢复（roll back)盘⾯到上⼀个猜测前的状态，换⼀个⽅向⾛⼀步。如果⼀个点所有的可能连接⽅向都失败，就返回到上⼀级，在上⼀级恢复到上⼀次猜测前状态，进⾏⼀次新的猜测。
整个过程就是⼀个典型的深度优先递归搜索过程。
从⽅法上来讲，其实没有什么新意，不过在具体实施上，还得先解决⼏个问题。⾸先第⼀个，定式应该选哪⼏个？如果仅仅只是以上说的⼏个定式，那其实⼤部分还是得靠猜，性能肯定好不了，⽽且总的定式有哪些呢？我也没空去研究，于是我⼲脆先编了个程序，算出了所有
2*2⽅格内所有可能的连接⽅式！⽐如这些：
⼜或者这些python新手代码错了应该怎么改
有了这些所有可能的连接⽅式，在程序上就可以将所有符合当前2*2⽅块中的数字和现有连接/禁⽌关系的连接⽅式都匹配出来，那么，所有可能的匹配⽅式中，如果某个连接都存在，那这个连接就必然存在；反之，如果某个连接都不存在，那这个连接必然禁⽌。举个例⼦，在3
3 ，1 1 这个组合中，必然会连接或禁⽌的线有这些
在实际盘⾯中，很少有所有4个格⼦的数字都被设定的情况，所有实际上需要尝试空⽩块中所有可能的数字组合，⽐如这个，需要尝试 从3 3，1 0 到 3 3 ，1，3这些组合。当然，好消息是实际上有些组合是不可能的，另外，如果有⼀些边已经被设置上了确定的状
态，那么就可以排除很多可能，⽐如如果是这个样⼦，则它实际上只有这⼀种可能了，我们可以放⼼地连接和禁⽌相应的线。
另外，这个2*2数字⽅块，实际上有3*3个端点，它实际上是⼀个3*3点⽅阵。⽽每个点有上下左右四个⽅向的连接。在2*2⽅块中的连接已经画出来了，但每条线实际上是必须向外延伸的。在四边中⼼的点上，如果在图中只连接了⼀端，那么意味着它向外连接出去，⽽四个⾓点
则可能会有两个⽅向 ，⽐如这个连接，实际应该是或者或者另外⼏种可能，视其⾓点的连接状态⽽定，每个⾓点，如果没有连接或有⼀ 连接，则外部会有两种可能的连接状态，是⼀个2的组合的关系。
道理想明⽩后，接下来是怎么编程了。为了减少⽐对的运算，我把每个⽅块内的每种可能数字设置⼀个位来表⽰，⼀共也就0到3这4种可能，⽤4位就可以了，如果⼀个格⼦⾥的数字已经被指定了，那么它就只有对应的哪⼀位被置位，如果没有设定，就先把4位都置上，再在运⾏过程中根据其周边的连接情况进⾏修改，具体的说，周围每连上⼀根线，它的最⼩可能值就少⼀位，每被禁⽌⼀根线，它的最⼤可能值就少⼀位。在进⾏⽐对时，把2*2格⼦⾥的4个4位掩码组合成⼀个16位掩码，与每个定式的掩码⽐较，如果定式的掩码各个位都被包含在其中，则该定式是⼀种可能的组合，运算上就是⼀个简单的先位与再判等的运算。
同样，我把每个点的4个⽅向的连接状态和禁⽌状态也⽤分别⼀个位表⽰，⼀共4位连接状态和4位禁⽌状态，⼀个3*3的点阵组合成⼀个36位的连接状态字和禁⽌状态字。因为现在都是64位的系统，我也没在意字长超过32位了。实际上连接和禁⽌状态是有重复的，⾄少中间这个点的完全不需要，已经被
其四周的点涵盖了，如果要在32位系统上实现，可以很简单的把中间这个点去掉就变成32位的了。 与定式的连接关系进⾏位⽐较判断，这要⽐较两次，⼀次是当前盘⾯中所有已连接的线在定式中必须有，通过位或运算再与定式判等可得，另⼀个是当前被禁⽌的线不能在定式中存在连接，通过位与运算判0可得。总之，使⽤了掩码以后判断都是位与或⾮的运算，速度快多了。
当得到了⼀堆所有的可能连接关系后，把这些定式的掩码再进⾏⼀次与运算，所有定式中都存在的连接肯定是必然连接。把所有定式再做⼀次或运算，所有定式中都不存在的连接必然要禁⽌。执⾏这些动作，然后再在被修改的点的附近反复进⾏这种匹配操作。
⾄于这个附近怎么定义，我也没想太多，就选了以这个点的左上⼩⽅块的4个点为左上顶点的4个3*3点⼩⽅块进⾏新的匹配，实际效果还不错，很多简单的盘⾯经过这种操作连任何猜测都不需要就直接解决了。
以上是有匹配结果的，可见如果盘⾯上现有的条件越多，可以匹配的定式就越少，其共性的边也就越多，可确定的也就越多，这也是每次在被改变的点附近进⾏新的匹配的原因，因为信息增多了。不过如果⼀个2*2盘⾯没有⼀个定式可以匹配，那就⼀定不对了，表明此路不通，需要回滚了。
以上是定式匹配，实际上除了定式匹配，每⼀步连接或禁⽌操作都可以推导出⼀些必然的结果，可以直接执⾏，因此在连接和禁⽌操作中也是⼀个递归的操作。
⼀次连接操作的流程⼤致是这样的：
1，判断本次连接可不可⾏，我设的条件有是不是已经禁⽌，是不是已经在已知的失败盘⾯中，是否连接点已经有两个连接了（形成交叉），是否会让⼀个格⼦周围的边数超过设定，会不会形成⼩环。如果有违反以上规则的，返回失败标识。
2，如果通过了检测，就保存本次修改会改变的状态值到⼀个记录列表中，然后修改相应的状态值
3，推导本次操作后⼀些可以⼀步得到的结果，我设定的判断有，如果已经让⼀个格⼦⾥的数字被满⾜，则可以禁⽌该格⼦所有未被连接的边，如果⼀个端点已经有两个⽅向被连接，则禁⽌另外两个⽅向，如果新连接端点已经有两个⽅向被禁⽌，则它仅剩的⼀个⽅向必然要被连接，如果新连接的端点与旁边的⼀个端点连接会形成⼀个独⽴的⼩环，则禁⽌这两点之间的连接。以上的操作如果任意⼀个出现失败返回，则返回失败标识，此后会被回滚。
同样，禁⽌操作也是这个流程，
1，判断禁⽌操作是否可⾏，包括是否已经被连接，是否会让⼀个有数字的格⼦剩下的可⽤边少于所需的值，是否会让⼀个有⼀点连接的端点形成3个⽅向的禁⽌从⽽成为死路，如果有以上情况，返回错误标识
2.如果没有以上情况，保存会被改动的状态，修改状态值。
3，推导必然会导致的结果，包括如果⼀个有数字的格⼦所剩可⽤边正好等于该格⼦所需的边时，连接剩下的这些边。如果⼀个有⼀端连接的端点被禁⽌了两个⽅向，只剩⼀个可⽤⽅向，则连接该⽅向。如果⼀个⽆连接的端点被禁⽌了3个⽅向，则禁⽌最后⼀个⽅向。以上操作如有任意⼀个返回错误，则返回错误。
在连接和禁⽌操作中如果返回错误，则需要进⾏撤销操作，撤销到最近的⼀次猜测前的状态。为了便于执⾏撤销操作，需要在每⼀步修改状态前保存需要修改的状态。每次操作会被修改的状态包括两个端点的连接状态和这个边的两个相邻格⼦的数字状态。另外还设定了⼀个操作累加编号，这样便于指定回滚到哪⼀次操作。这个号⼀直累加，我同时还把每次操作记录到了⼀个log⽂件中，后来对我bug起了很⼤的作⽤。
这⾥说⼀下我所⽤的数据结构。为了图⽅便，我⽤⼀个格⼦类来记录⼀个格⼦和其左上顶点的状态，现在看起来如果把格⼦和点分开来存所需空间和记录内容会少⼀些，不过懒得动了。每次修改就会涉及三个格⼦类的改动，我叫他们起点，终点和邻居。这个类⾥⾯的信息有设定的数值，可能的数值掩码，点的连接关系和禁⽌关系掩码，当前周边有多少边连上了或禁⽌了等等，最后还有两个参数，⼀个叫线号，⼀个叫信息号，等会再说这两个。我把这些格⼦类组成⼀个⼆维数组，⼀个m*n格⼦的盘
⾯，实际上有(m＋!)*(n＋1)个点，⽽我为了避免每次操作时进⾏越界判断，⼜在左边和上边加了⼀⾏⼀列格⼦，所以⼀共是（m＋2)*(n＋2)个格⼦。在初始化时，将四个⾓格⼦设为0，四个外边的⾏列格⼦⾥的可能的数字掩码设为3，也就是可能为0和1，在禁⽌盘⾯主体向外的连接关系，这样就把真正的盘⾯包起来了，⼜不⽤每次去判边界和进⾏复杂的边界处理，付出少少的空间代价，⼤⼤减少代码处理的复杂度。
好了，接下来说说线号这个东西。因为每次匹配和猜测都要从线的端点进⾏判断，特别是还要判断是否构成⼩环，所以我设了⼀个列表来保存每个线段的两个端点，为了区分这些线段，给它们每个设定⼀个线号。线段的操作有三种，分别是：
1，产⽣⼀个新线段，在连接两个没有任何连接的端点时就会产⽣⼀条新线段，这时给它分配⼀个线号，然后存到当前存在的线段列表⾥。新信号是单调增加的，保证每个都是新的没⽤过。
2，延伸⼀个已有的线段，像贪吃蛇⼀样长长，把线段列表⾥原有的端点替换成新的端点。
3，合并两个线段。这个最⿇烦，我设定是⼤号吃⼩号，当然也可以⽼号吃新号，我在这两个⽅案⾥想来想去哪个号，最后发现其实都⼀样。被吃掉的就要从当前存在列表⾥移出，可不能就丢掉了，加上凶⼿的编号存到⼀个已移除的列表⾥，将来说不定还有诈⼫的机会。记得把新的列表⾥的端点改成新的端点，还有把原来被吃掉的那个的⼀个外侧端点（也就是合并后的线的⼀个端点）的线号改成当前
的新线号。
通过线号，寻端点和判断⼩环的操作就简单多了。⽽在回滚操作时，也需要恢复线号和线号列表中的内容，所以有关的信息也需要保存在操作记录中。
到这⾥基本上就说完了，实际运⾏效果，我从⼀些数回游戏上抄了⼏个图来测试，基本上简单难度的图不⽤猜测都能完成，难⼀些的图就需要猜测⼀些。然后我在这⾥因为有些BUG，死活解不了，花了⼏天的时间，最后不得不把过程写到⼀个log⽂件中⼈⾁复盘才发现了问题所在，这⾥就要讲下我这次最失败的设计，就是前⾯说过的信息值这个东西，更准确的说，不是信息值本⾝不好，⽽是我实现时⽤的数据结构不好，没有把信息值放到格⼦类⾥⾯，⽽是另外列了⼀个结构数组，容易出错，这个错让我花了⼤量的精⼒去排查。开始怀疑是回滚操作没有完全恢复盘⾯，于是想办法排查了回滚前后的状态，后来发现回滚操作是对的，但是回滚的位置没弄对。除了这个BUG后还是不对，只能⼜去⼈⾁复盘第⼀次猜测前后的盘⾯状态，最终发现是因为数据结构的叠床架屋，造成信息结构和格⼦类中的数据在回滚后没有良好同步更新，造成匹配定式时计算连接状态掩码错误。
⽽信息值本⾝，还是证明很有⽤的。因为要进⾏猜测，那么当然是从已知条件⽐较多的地⽅开始⽐较好，为了表征⼀个块的信息含量，我设定了⼀个信息值，⽐如设定了数字的，信息值肯定要⼤⼀些，⽽3和0的值肯定要⼤于2和1的值，同时没增加⼀个连接或者禁⽌，也要增加⼀些信息值，具体增加多
少，其实也就是随便拍了个脑⽠定了个数。然后在每次需要猜测时，从所以线的端点⾥，挑⼀个综合信息值最⼤的来进⾏尝试。这个综合信息值也就是说不是这个块单独的信息值，⽽是它周围的信息值的总和，⾄于周围多⼤，我还是拍个脑⽠，先设成以该点为左上顶点的2*2⽅格了，其实现在想想应该以该点为中⼼的2*2⽅格或者更⼤⼀点的范围⽐较合理。不过当时以调通为先，没想那么多了。⽽且为了除BUG，我⼀度屏蔽了这些可能会引⼊BUG的代码，简化流程，最后调通时这个功能实际上是没有的。⼀时⾼兴试了⼏个简单的图，都是秒过，感觉没必要再折腾了。后来从⼀个ipad游戏上抄了⼀个最⼤的图，这下就觉得有点慢了，花了⼤概30多秒，查了⼀下LOG有20多万步，哎呀妈呀，实在有点多呀，想起还有这么个功能被屏蔽着，就打开试试吧，这⼀开不要紧，刚点下去就出来了，吓得我还以为是上次的结果没清掉（我这游戏有个存答案的功能），⼜仔细的重新开游戏，看看没有存下答案，再点下去，还是秒过，这下真把我乐坏了，查看了log，才两千多步，百倍的差距啊！这还是随便排脑⽠设计的信息值函数，就有这么⼤的威⼒，所以算法的改进才是根本，代码的优化只是锦上添花。
最后不得不说个事，我⼀度信⼼膨胀，从⽹上了个40*50的超⾼难度地图，结果可耻的失败了。想了⼀下，我这种简单的深度优先在处理超⼤版⾯时深度太深了，肯定是不⾏的。改进的⽅案应该是采⽤分块的⽅式，将⼤图分成⼩块，算出每个⼩块中的所有可能，再与邻近的块尝试可能的拼接。举个栗⼦，⼀个3*3的盘⾯，我现在已经有了所有2*2的定式，那么先从左上开始，匹配所有可能的2*2定式，
这也是我在程序⾥做的事，但是匹配完后不是寻确定边就完事了，⽽是将每个匹配上的2*2定式设置在盘⾯上，滑动⼀格，去试试旁边的2*2能够在满⾜这个匹配的边缘条件下能匹配多少，最后就得到了⼀个能够满⾜这个3*3的盘⾯的所有定式。这种匹配结果保存下来，即使回滚也不⽤⼀滚到底。分块的思想实际上就是把定式再扩展到更⼤的尺⼨。当然，太⼤了这个可能性太多，都存下来不现实，因此⼤于⼀定的时候，不是靠穷举⼩⼀些的定式来拼接，⽽是在其中采⽤猜测-推演的⽅式⽣成，每个块⾥推进到边界就不再向外，这样每次回滚也就只需要回滚⼀个⼩块⾥的内容，保存也只需要保存⾥⾯的⼏个猜测点就可以了，需要的保存值要少⼀些。当然内存够⼤的话多存点也没关系，分成多⼤的⼩块呢，我觉得10*10应该差不多。
要实现对这种超⼤版⾯的解算，⽤python估计是不⾏了，得⽤C才⾏，因为分块，所以可以⽀持多线程并⾏，效率还可以⾼⼀些，因为要进⾏⼤量的特征字⽐较，所以最好再⽤上超标量指令集，要不再上个CUDA？嗯，我觉得还是算了吧。我就是玩玩游戏，犯不上和它拼命。反正⼀般的图都能秒出了，够我⽤了。
游戏放在我的下载⾥了，代码⽐较乱，完整记录了⼀个不幸误⼊泥潭的倒霉蛋的挣扎痕迹，需要的同学⾃取吧。⽤关键字Slither link搜索，⽬前还是全站唯⼀，唉，这个游戏真够冷门的。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。