[TML小组]<绝对原创>数独雨林原理

本帖最后由 MojeDes 于 2016-8-9 10:46 编辑

大家好，我是来自TML小组的夕阳延辉。

自从看到帕西的解数独游戏视频（地图原作者是Az大大）以及那时候乾坤正在做五子棋AI，于是我突发奇想，打算在MC里面做一个智能解数独。

终于，历经千难万险，我做出了这个东西。

原帖链接：http://www.mcbbs.net/forum.php?mod=viewthread&tid=617311&page=1&extra=#pid10719406

那么，废话不多说了，我来讲讲它的原理吧。

在开始之前，我们得明确一个方案，这里我用粗略的流程图来表示一下：

现在就是详细讲解一下了：

首先做一个棋盘，棋盘边上放置4个盔甲架（视情况而定），这些盔甲架（你也可以用其他任何实体用来探测）名称分别叫find（遍历整个数独的东西）、col（列Column的缩写）、row（行）、box（宫）。

他们的作用分别是：find用于全盘探测和深度搜索、row用于行探测、col用于列探测、box用于宫探测。

·创建一个记分板，名字叫round（随你定），类型为dummy

开始的时候，玩家会按下按钮，那么这时就得将find的round设置为0了（由于一些原因（后面会讲），我们需要给find规定round为3的时候才能触发开始指令），那么相关的CB就需要根据find的round来执行。

·先召唤一个叫做start的盔甲架

·在创造一个记分板，名字叫times（随你定，以后不做赘述），类型为dummy

看下面这个图，RCB（循环型命令方块）一直执行给start的times+1的指令；

第一个CCB（连锁型命令方块）是一直把基础流程（由探测和唯一法填数组成的CB链）的CB（脉冲型命令方块（有时候是泛指所有类型的CB，注意区别））激活（激活后再关闭，才能确保下一次能够激活），这个CCB是每一个游戏刻都会触发的，但是下一个CCB是每4个游戏刻才触发一次（3游戏刻触发一次会出现一些问题），因为考虑到后面的流程，所以必须要隔这些时间再执行一次。第三个CCB是当start的times为5的时候将分数改回0，以便达到循环的目的。第四个（可忽略）是用来告诉玩家正在使用唯一法解数独（当find的round=1的时候）。

(有些CCB是空指令的。。。我懒得删掉了，楼主是个大懒货，嘿嘿)

基础流程：

·召唤一个叫做times的盔甲架，用于执行流程

流程的第一步是让find进行全盘搜索。首先，让find往某个方向tp

大概是这个样子。单步tp很容易，下一行的传送就需要用到detect了，把下一行传送的CCB做到单格传送的后面，这样的话，find单格传送到脚下有xxx（随便一个方块）的时候就要以find为基础，向某轴-9，某轴-1（视情况而定，不要生搬硬套）进行传送。在这个CCB的后面是检测find的脚下是不是另外一个方块，如果是，则将find的round设置为1，并且将其传送到原来的地方。紧接着的CCB是召唤一个标记（可以是AreaEffectCloud（简称AEC）或者ArmorStand(简称AS)等实体，这里推荐用AEC，不会造成太大的卡顿）。怎么召唤呢，当find的位置是x的时候（用detect检测方块），则召唤名字为x的AEC，并且给该AEC加上yes标签(tag)*这里要注意，千万不要以为我是多用了9个CCB，因为考虑到后面的流程，每当AEC有方块的时候就要加上yes标签*；当find的位置是空气的时候，则依次召唤名字从1到9的AEC，并给它们的tag加上not，表示待选状态。

为什么find的原处有一个石英台阶？因为虽然find被tp回去了，但是CB链并不能停下来，所以以防它召唤AEC，所以需要在那里放置一个毫不相关的方块。

好，接着说。在那之后，还要加上remove掉带有yes标签的AEC中的not标签（因为如果你不remove掉not的话，到时候可能会产生干扰）。

·创建一个记分板，叫做count，类型为dummy

接下来的一个CCB是给times（盔甲架）的times（分数）一直+1（每4游戏刻一次），当times的times为1的时候执行显性唯一解填数（单元格唯一解填数），如何填呢？需要用execute来给每一个not标签的AEC加count分数。只需要用execute探测每一个not标签的AEC，然后给其范围0内（原处）的其它AEC加1分count。假设一处有3个not标签的AEC，那么execute首先选中3个AEC，然后选择器选中原处的3个AEC，各加一分，而又因为是以3个AEC为基准，所以会加3次分，那么，这里的AEC就有3分了。

记得要加上改auto为0b的CCB！

当探测到有count=1的AEC的时候，下面的模块就会开始填数

这个是通用填数模块，几处都要调用它，所以我把它单独作为一个模块进行调用。

我们接着说流程，执行完这个以后，就需要调用行列宫删数了。

·召唤一个叫做cround的盔甲架，用于执行删数流程

那个RCB是执行单元格删数，红圈范围内是执行行列宫判断的基础。首先给cround的round+1（round默认为0），当cround的round=1的时候clone用来执行（xíng）行（háng）的彩色玻璃，clone到数独盘的下方，当round=2的时候执行列判断，3的时候执行宫判断。然后在最后一个CCB判断，当round=3的时候，将round归0，不要忘记改auto的事情（很重要很重要）！改auto最好放前面，或者在流程执行的时候弄2个改auto的，你还可以用setblock进行destroy。

·建立9个记分板，名字从count1到count9。

中间这三列CB链用来探测每行每列每宫的隐性唯一解。那就需要用到之前的三个盔甲架（box、row、col）了。将它们进行tp（不做赘述），所经过的行（或列或宫）的下面都要fill石头（不过首先要fill为空气，切记，fill石头仅限于行或列或宫，不是全部fill）。然后用execute探测AEC下面2格（数独盘底下），并给row的countx（根据探测的数字来定x）+1分，看代码：

execute@e[type=AreaEffectCloud,name=1,tag=not] ~ ~ ~ detect ~ ~-2 ~ stone 0 scoreboardplayers add @e[type=ArmorStand,name=row] count1 1

如果countx是1分，那么就探测回来，给那个AEC的count设置为1，接着调用唯一数填数的模块即可。

execute@e[type=ArmorStand,name=row,score_count1=1,score_count1_min=1] ~ ~ ~ execute@e[type=AreaEffectCloud,name=1,tag=not] ~ ~ ~ detect ~ ~-2 ~ stone 0 scoreboardplayers set @e[type=AreaEffectCloud,name=1,r=0] count 1

如果这里依然利用刚才用来删数的那种方法（clone彩色玻璃）是不太好的，这样可能就需要3*80的CB还要多！只不过刚才那种方法会相对快些（说白了是我懒，不想弄那么多CB）。

接下来就是重头戏了！

深度搜索+剪枝：

如何进入深度搜索呢（如何探测数独已无法使用唯一法呢）？

·建立一个记分板，叫做depth，类型为dummy

上面这个CB链有两个功能，一是探测是否有81个含有yes标签的AEC，二是检测数独盘的上一次状态是否和这一次一样（没有填任何一个数，也就是无法使用唯一法了），如果一成立，则将find的round改为3，并重置所有分数，告诉玩家：数独解决完毕；如果二成立，则关闭执行唯一法流程的RCB，开启深度搜索流程。下面这个CB链是将find的round改为2（执行深度搜索流程），然后把所有含有not标签的AEC的depth分数改为-2333（定为一个小于-80或者大于81的数即可），后面我们会用到。

如前面一样，首先要给find进行tp（红色部分）。蓝色部分是探测find是否归位（也就是数独是否解决完毕）。白色部分是如果还没到最后，则继续解。这里蓝色部分用了一个条件制约的CCB，当find归位之后就不会执行继续解下去的模块了。

·创建一个记分板，叫做sort，类型为dummy。

·召唤一个叫做sort的盔甲架，用于给单元格内待探测的数独排序和探测是否为无解单元格，sort的sort默认为1分。

看到第一层的CB链，以一个排序接一个加分，看代码：

/execute @e[type=ArmorStand,name=find] ~ ~~ execute @e[type=AreaEffectCloud,name=1,r=0,tag=!kill] ~ ~ ~ execute@e[type=AreaEffectCloud,name=1,r=0,tag=!x,c=1] ~ ~ ~ scoreboard players operation@e[type=AreaEffectCloud,name=1,r=0,tag=not,c=1] sort =@e[type=ArmorStand,name=sort] sort

tag为kill是被剪枝掉的数，x是本次分支内，这个数的分支已确认无解的数（注意，c=1的意思是选择它自己，而且前面制约了条件tag=!kill，后面就也会包含这个制约，所以无需担心（这里十分感谢Potter_Lee的帮助））。这就是剪枝后的东西，具体剪枝后面会讲。每当排一次序，sort的sort就要+1，以达到排序的目的，排序完后，sort的sort就要恢复为1分。

有的人可能会问，为什么只要执行sort为1分的呢，因为每次探测都会重新排序，就会一直有sort=1的AEC，除非它是无解单元格。

第二层的CB链是判断单元格是否无解，首先一个是给sort为1分的AEC加上叫做try的tag，表示这个数将要被尝试。如果存在sort为1分的AEC，那么条件制约的CCB就会执行剪枝搜索，如果不存在sort为1的AEC，那么，就会进行回退处理，回到上一层。现在先来讲讲剪枝是如何执行的吧。

其实和之前那个行列宫删数是差不多的，只不过这里不是杀死AEC，而是加上一个kill的tag，如果你杀死这个AEC，到时候到退回来就不好办了，对吧，那么先看一个示例代码：

execute @e[type=ArmorStand,name=find] ~ ~ ~execute @e[type=AreaEffectCloud,tag=try,r=0,name=1] ~ ~ ~ detect ~ ~-2 ~minecraft:stained_glass 1 execute @e[type=AreaEffectCloud,tag=!kill,name=1] ~ ~~ detect ~ ~-2 ~ minecraft:stained_glass 1 scoreboard players tag@e[type=AreaEffectCloud,r=0,c=1,tag=!try] add kill

因为考虑到后面要根据层数移除本层的kill标签，所以这里排除了给带有kill标签的AEC加kill标签（好像是多余的。。。）。这里就要多加几个CCB了，当round=3的时候，就要执行tp（给那个CB改auto为1b），而且还要给刚刚加上kill标签的AEC赋值目前层数。还有一个CCB是给sort的层数（depth）+1。那，如何探测刚刚加上kill标签的AEC呢？在之前我们将所有空格处的AEC（含有not标签的AEC）的depth改为了-2333，那么就只要用选择器检测depth分数为-2333而且tag=kill的AEC，将其depth进行赋值即可。

下面是对无解单元格的处理。

首先执行上面这一层的CB链，如果这个单元格是含有yes标签的AEC，就直接跳过就行了，如果真的是无解单元格，那么才执行下面这一层的CB链。

如何处理呢？

在倒退之前先要移除本层所有的状态，将其还原到刚开始执行深度搜索法的时候的状态。那么需要移除哪些状态呢？kill标签、x标签、try标签、深度(好像就这些了)。

如何探测是否为上一层呢？还记得吗，只有sort执行成功才能将深度+1，那么find到了无解单元格，深度是不会变的，那么久将所有含有try标签的AEC的深度-=sort的深度，如果为0，则将find传送过去，记得在将它们的层数加回来。先别急者把深度-1，还有一些状态没移除。很简单，只要探测层数相同，就移除kill标签、x标签。然后因为盔甲架已经tp回上一层了，那么给盔甲架所在单元格内的AEC的try改为x，那么sort会根据这一点往后执行一个数，接着再给sort的深度-1。执行完这个以后，改auto就只能改排序的那个了(总不能刚tp回来又tp过去吧)，然后再次执行流程，如此循环往复。

继刚才那个探测find是否归位接着讲，这里是将所有AEC的tag改为yes并remove掉not，下面这个是执行填数的CB链。然后调用探测是否为81个数都填完的模块，解数独就这样结束了。

其实有一种方法可以省去开始的探测，就是每个单元格都弄一个AEC，大概能省去160多游戏刻。。。

教程到此结束了，谢谢大家的观看，可能还有可以简化的地方，如果大家有什么更好的方法，欢迎大家提出或者自己实践！至于检测无解数也不是很难，只要在深度搜索那里加一些探测的CB就行了，然后调用，如果达不到81，则视为无解。

希望大家能喜欢，给点金粒吧。

最后，祝TML小组一周年快乐！

[TML小组]<绝对原创>数独雨林原理

回复: