半位腾挪随心记

cjcjc

最近几年困难的半位关卡越来越多，对半位腾挪的技巧要求比较高，但是其中变化很多，非常复杂且不容易总结规律。虽然有20603大师建立的理论在前，但是在解关和设计过程中还是会遇到一些令人摸不着头脑的结构。我也推了不少半位关卡，积攒了一些经验，但是实际推的过程中也总是糊里糊涂，很难摸得到头绪。之前有很多技巧和规律，不知道怎么用语言准确且清晰地表达出来，也有一些内容比较零散，不成体系，还有更多的东西是我也没有把握的，所以没有做过关于半位腾挪的分享。这次以一个小问题为契机，开一个帖子，随便记录一些我对半位腾挪的理解和认识，也记录一些分析的方法和过程。目前写的内容不太多，后面可能会慢慢补充。我分享的东西未必是普遍的或者具有代表性的，也有一些猜想的东西未必是准确或者严谨的，主要起一个抛砖引玉的作用，也希望大家多发表意见，分享自己的想法。

ps 里面有一些词我是乱编的，大家试着理解一下，如果有更好的想法也可以提出来

cjcjc

1.一个无解的半位关卡

这两天和an版主讨论了一个关于半位腾挪的问题：
一类全部连通的，全程半空的关卡，是不是肯定有解？
如果有无解的情况， 那是怎样的情况？

这个问题的答案我认为是否定的，会有一些无解的情况。对于其中一种情况，我举了一个例子：

-#######-
##---*-#-
#@-***-##
#-------#
#*-**-*-#
#---*.*-#
#-***-$-#
#---*-*-#
#########
Title: 死角
Author: Kevin29 + cjcjc
Comment: 无解

这一关由Kevin29生成的一关的局部调整得到。很显然初始状态只有B3这一个奇半位，目标状态也没有局部的死锁，所以全程腾挪都只有一个奇半位，不涉及半位的转换或者增加。这关是一个无解的关卡，用解关器可以得到这个结果。或许有的人可能会觉得这关之所以无解是因为整个关卡比较小，腾挪的位置不够造成的。但是我认为死锁的原因是G7这个箱子，在只有一个奇半位腾挪的情况下，想要推开且不靠下面或者右面的墙，是无法做到的。也就是说，这个结构是一个半位的死锁结构。下面我来具体解释一下。

cjcjc

首先，先解释一下“腾挪的位置”，指的是一个半位腾挪的局部中，墙和墙之间的距离（这里的墙也可以是不能动的箱子），我比较喜欢管这个叫做宽度。举一个例子：

189期主关，红色区域的局部宽度是3，蓝色是2，绿色是1。根据我的经验，宽度大于3的局部腾挪一般是比较松的，大部分形状都可以腾挪到；宽度是3的局部的腾挪通常是比较紧的，甚至可能是唯一的或者是无解的；宽度是2的局部的腾挪比较不自由，通常只能支持箱子单向的移动；宽度是1的局部不支持腾挪，相当于一个只能“路过”的狭道。关于宽度，不是这次讨论的重点，而且我也不能特别准确的描述其中的规律，所以只简单提一下。
（这里插一段题外话，我总结出来的影响半位腾挪难度的三个要素分别是半位数量、宽度和箱子自由度。半位数量越多，腾挪越容易，反之半位数量越少，腾挪越难，这个规律还是比较显然的。宽度越大，腾挪越容易，反之宽度越小，腾挪越难，03大师有很多关卡，里面有一些“尖”、“跳”、“飞”的墙的设计，就是为了增加腾挪难度。至于箱子自由度，举个例子，下图的中间三个箱子虽然没死，但是不能直接推动，所以是“不自由”的，自由的箱子越多，自由度越高，腾挪越容易，反之自由度越低，腾挪越难。

菱形关卡和棋盘格关卡里面通常会有很多不自由的箱子，自由度太低有可能会导致关卡无解。这些都是我的经验，没有严谨的理论和表述，仅供参考。）

cjcjc

回到《死角》这一关，这关的死锁会不会是宽度不够造成的呢？我认为不是，一是关卡上下和左右的宽度都足够进行自由的腾挪，二是我也扩大关卡测试过，扩大的关卡也是无解的。
扩大的时候需要保证全局只有一个半位，半位奇偶性和右下未到目标点的箱子的坐标的奇偶性相反。扩大的时候需要把握一下分寸，扩的太大了解关器就解不出来了。下面这关我推测无解，但是没有解关器辅助验证。

-----#####-
######---#-
#--*---#-#-
#--*****-#-
#**@-*-*-##
#---------#
#**-***-*-#
#-----*.*-#
#**-***-$-#
#-----*-*-#
###########
Title: 死角-2
Author: Kevin29 + cjcjc
Comment: 初始版本扩充得到，推测无解

下面我们试着分析一下怎么把“死角”的箱子腾挪走。先看一个化简的情况：
-#######-
##---*-#-
#@-***-##
#-------#
#*-**-*-#
#---*.*-#
#****-$-#
#-----*-#
#########
Title: 死角-3
Author: Kevin29 + cjcjc
Comment: 初始版本的简化情况，无解

这一版下面的墙只有一个箱子，把其他元素全部隐藏，只看G7这个箱子。因为G7不是一个目标，G7的箱子一定要离开这个位置，往右或往下会造成箱子靠墙，点位不足死锁。如果是往上的推动，H7H8两个位置一定是空地，箱子推走后G7也是空地，因为向上的推动G8需要站人，所以G8也是空地，那么G7G8H7H8是四个相邻的空地，构成了一个偶半位，这关全程只有一个奇半位，所以这一推是不可能的。如果是往左的推动，同理可得G7H7H8是三个空地，如果G8是空地，那么和上一种情况一样是不可能的；如果G8是箱子，那么这一推后，F7F8G7G8如下图所示，形成一个对角的偶半位，也是不可能的。综上，G7的箱子不可能离开这个位置，这关无解。

cjcjc

回到最开始的情况，这时下面的墙有2个箱子。想要推走G7的箱子，和上面的分析一样，可以看到上、右、下三个方向是不可能的。向左推可能出现下图的情况，因此是可能的。



这里右下的腾挪其实目标就是利用半位构建一个类似这样的通道：



然后G7箱子的往左两步推动其实就是一个简单的“零空位”腾挪。之后在进行一些简单的腾挪就可以过关。下面我来说明这个通道是无法构建出来的。

（这里再插两段题外话
1.半位常见的形式有两种，一种是四个相邻的空地，另一种是两个箱子对角或者箱子和墙对角，例如：



这个图里一共是外面的通路是一个整位，红框是两个偶半位，蓝框是一个对角半位。把C4箱子往右推一步，可以看到外面通路整位不变，左上的偶半位也不变，右下的偶半位挪到左下，对角半位挪到左边中间，是一个奇半位。再把D3箱子往左推一步，外面通路整位不变，左下偶半位不变，左上的偶半位挪到右上，左边中间的偶半位变成中间的对角半位，奇偶性不变。可见两种对角半位的奇偶性是一样的，都是对角方块中右上或者左下的坐标的奇偶性。

2.我经常用到的半位腾挪技巧有两个，一个是直接用半位腾挪调整箱子位置，另一个是利用半位构建通路，再用通路进行“零空位”腾挪。有一定半位腾挪经验的人可能看这些笼统的描述就已经理解个大概了，至于准确的或者严谨的定义，我还没想好怎么描述或者表达出来。）

cjcjc

考虑下面的简化情况：
-#######-
##---*-#-
#--***-##
#*------#
#--**.*-#
#-**@-*-#
#-*-$-#-#
#---*-*-#
#########
Title: 死角-4
Author: Kevin29 + cjcjc
Comment: 想要解开初始版本的一个预想的中间步骤形成的关卡，无解



这里的箱子布局由最初版本通过一些简单的腾挪就可以得到。因为这一步骤是为了推动G7箱子的前置工作，所以需要把G7变成墙，否则容易进入依赖循环中（通俗地说，就是想要推到状态A必须先推到状态B，但是想要推到状态B又必须先推到状态A，所以A和B都不可能推到）。至于目标点的分布则是取了最简单的一种情况，其他可能的情况是类似的。

考虑《4》的逆推。



想要把一个箱子拉到E7，只能从E6往下，或者D7往右。先考虑E6往下，如果这一步成立，那么拉这一步前，E7E8F7F8都是空地，形成一个偶半位，这是不可能的。如果是D7往右拉，再考虑两种情况：如果E8是箱子，B8不是箱子，那么D7D8E7E8形成一个对角偶半位，不可能；如果E8不是箱子或者G8不是箱子，那么需要先拉E8这个箱子，在E7是空地的前提下拉E8箱子，会使D7D8E7E8形成一个对角偶半位，也不可能。综上，这个关卡是无解的。进而初始版本是无解的。

所以对于最初的问题“一类全部连通的，全程半空的关卡，是不是肯定有解？”，答案是否定的，《死角》就是一个反例。不过这只是其中一种情况，还有宽度不够造成的死锁和自由度不够造成的死锁，以后有机会再分享...