2019-3-29 13:31:11 上传
下载附件 (38.31 KB)
推箱子游戏中半位空间的奇偶属性与磁铁效应
文 / Zou Yongzhong
通常半个箱位是指占位2×2的小正方形，这里简称“半位”。为避免“2个半”的理解歧义，“2个半位”我在这里称之为“双半位”或“两处半位”。2018年9月12日我在讲关卡《二泉映月》的逻辑关系时，已经讲过半位空间的一些理论和腾挪要点，今天讲的应该算是两个定理吧，即关于半位空间的奇偶属性与磁铁效应，我称之为半位定理。这两个半位定理我在十多年前设计半位关卡时发现，前几年创作《失散之城》系列关卡以及比赛关卡《百尺竿头》时觉得有必要将其整理成文字。这次在第121期比赛关卡的设计中也运用了这个定理，所以现在把这篇文章整理发出来，相信更多人在看明白这个理论后能解开121期比赛关卡。
一、半位空间具有奇偶不变性。
图1 偶性半位和奇性半位
如图1，把半位空间左上格A对应的坐标横轴数字与竖轴数字相加，得到的数是偶数的，我称之为“偶性半位”或“偶半位”，反之，称之为“奇性半位”或“奇半位”。半位空间的坐标以左上角即A点的坐标来描述。通常横向坐标以字母标注，纵向坐标以数字标注，比如图1的F4半位是偶半位。但这篇文章为便于区分奇偶，部分横向坐标也以数字标注，F4半位标为6-4半位。定理1：在一个关卡地图内，一处半位空间不论移到关卡何处，其奇偶性不变！
证明：有多种方式可以证明这一定理。
1、首先，用图解的方式直接证明：
图2、半位空间移动的几种常见情形
如图2，中间的小关卡正中是一个偶性半位空间，通过简单的变换，可以移动半位空间到6个不同位置。去除对称重复，我们分析下面图3的三种情形：
图3、三种颜色对应三种移位情形
我以前在讲半位腾挪理论时已经总结过，当半位空间移动时，其实是木箱向半位空间内移动，将半位空间置换到自己的位置。图3中，当木箱A向半位空间内移一格，半位空间就向A所在的方向移了2格。一个活的关卡，能够移动的木箱周围必然有搬运工可以占据的通道，木箱A之所以可以移动，是因为它左侧和右侧的通道空置，将木箱A向右推一格，就意味着将右侧通道置换到左侧，在图中，就是将第4列通道移到第3列，与原先第2列的通道组成新的半位空间，原先的半位空间从第4列被平移到了第2列，奇偶性不变。
木箱B的移动情形是类似的，但当B向下移动一格时，直观上并不形成新的半位空间，那是因为木箱C占据了1个角，这个角让新的半位空间的位置变得不确定。当我们把木箱C向左推1格，其情形就与推动木箱A相同了，半位空间向上平移了2行，其奇偶性不变。如果木箱C向上移1格呢？那正是木箱D和E的情形。
木箱D向上移了1格，使半位空间位置处于待定状态，如果木箱E再向下移1格，意味着木箱D让半位空间右移了1格，木箱E让半位空间下移了一格，半位空间就向右下方向斜移了1格，横向坐标和纵向坐标各加1，两者之和，其奇偶性仍然不变。
其实前两种可以算为一种情形，都是半位空间的平移。第三种是半位空间的斜移。除了这几种，更多半位空间的移动是比较隐蔽的，比如：
图4、复杂和隐蔽的半位空间移动
如图4，半位空间从下方移到上方，似乎看不清中间过程，好像推了这几只箱子，半位空间突然就跳到上面去了，中间看不到半位空间的连续移动。其实，这种复杂的移动也可以分解成图3的简单情形。半位空间在移动过程中其位置处于待定状态，移动过程中虽然看不到半位空间，但每一步都会产生位置待定的半位空间，且任何待定状态都是图3的两种情形（平移和斜移）之一。每一步状态分解如下：
图5、半位空间移动过程分解
移动步骤：
第1步：R，半位空间隐藏在待定位置（坐标）2-8和2-6，对应步骤分别为RldR和RluurD；
第2步：RR，半位空间隐藏在待定位置2-6和4-8，对应步骤分别为RrlluurD和RrdrU；
第3步：RrlluurR，半位空间隐藏在待定位置3-5、2-6和3-7，对应步骤分别为RrlluurRluuRlddrU、RrlluurRluuuurrdddLdlU、RrlluurRllddrrUdlluurD、RrlluurRllddrrUL；
第4步：RrlluurRluuR，半位空间隐藏在待定位置3-3、3-5和4-2，对应步骤分别为RrlluurRluuRU、RrlluurRluuRlddrU、RrlluurRluuRluurrdL；
第5步：RrlluurRluuRU，半位空间最终移到3-3。
从图5可以看到半位空间移动的连贯性。半位空间的移动，要么平移，要么斜移，其移动不论怎么隐蔽，都可分解成这两种状态，前面已对这两种状态的奇偶性进行了阐述。根据上述分析，半位空间的移动，其奇偶性不变。
2、再用反证法进行证明：
假设在一个关卡地图内，有一处半位空间在移动过程中改变了奇偶属性，比如从初始状态的偶半位变为某个状态的奇半位。由于半位空间的移动是连贯的而不是跳跃的（前面已经证明过，这里不再重复证明），那么不论变化多复杂，用了多少步骤，一定至少有一个步骤是直接从偶半位变成奇半位，我们只截取这个直接产生变化的步骤来观察：这个偶半位变为奇半位，意味着它向邻近的方向（横向或纵向）平移了1格，2×2的半位空间，平移一格产生另一处半位空间，原先空出来的位置加上这新的半位空间，就必然形成2×3的空间（如图6）。 2×3是一个完整的箱位，这与关卡的半位空间属性产生了矛盾。当半位腾挪过程中产生1个完整箱位时，必然在关卡内产生死锁（提前推死目标除外），比如图6中木箱7-4形成死锁。综上所述，这种奇偶改变是不可能的。
图6、半位空间移动1格
3、我们用两种方法证明了“定理1”：在一个关卡地图内，一处半位空间不论移到关卡何处，其奇偶性不变！这个理论有广泛的应用，在此举一个例子，如图7：
图7、两个关卡的死活判断
如果告诉你这两关一死一活，怎么快速判断呢？掌握上述“定理1”后，这两个关卡孰死孰活就一目了然了。要安全移出D7木箱，就会产生C7半位空间，这个半位是偶半位。左侧关卡M3处有一偶半位，移到C7位就有了过关的可能；右侧关卡L3处有一奇半位，无法移到C7位，所以它必然是个死关。
二、双半位空间具有磁铁效应。
一个关卡地图内若有双半位或多半位空间，它们之间具有同性相斥、异性相吸的磁铁效应。定理2：在一个关卡地图内，如果两处半位可以移动到邻近位置，具有相同奇偶属性的双半位不能合成一个完整箱位，具有不同奇偶属性的双半位可以合成一个完整箱位。
证明：这个定理的证明比较容易，我们对同性半位和异性半位分别进行证明。
1、同性半位相斥的证明：
一个关卡地图内若有两处以上的半位空间，任意两处半位移到邻近位置有两种情形：（1）错位相连；（2）对齐相连（横向对齐与纵向对齐是等价的）。
若是错位相连，那么如图8，左侧2处半位，右侧3处半位，错位相连的状态下，在半位空间内任意空格寄存1只木箱，均会阻挡搬运工的通道，形成死锁。所以同性半位错位相连不能合成1个完整箱位。
图8、同性半位错位相连
若是对齐相连，那么如图9，D4和F4双偶半位相连，就形成2×4的空间，这是1.5个箱位，关卡地图内多出半个箱位，必然在别处产生死锁（F3木箱死锁）。
图9、同性半位对齐相连
综上所述，同性双半位相连，要么不能形成有效箱位，要么产生死锁。同性半位相斥得证。
2、异性半位相吸。
这个是不证自明的，通常意义上的一个完整箱位是2×3的空间，它本身就包含1处偶半位和1处奇半位，也可以说，常规意义的2×3箱位，就是由异性双半位合成的。如图10，D3木箱和F3木箱分别向左右各移一格，B2半位（偶半位）和G2半位（奇半位）就在中间连成了1个完整箱位。
图10：异性双半位连成1个箱位
“定理2”是说，具有不同奇偶属性的双半位“可以”合成一个完整箱位，并非必然合成一个完整箱位，所以只要找到1个例证，便已证明（其实常规情况下都是可以合成的）。这里需要注意的是：
（1）并非所有完整箱位，都是由异性双半位合成的。如图11的绿色方框，这个箱位并非由双半位合成。
（2）并非所有异性双半位都能合成1个完整箱位。如图11红色方框，这是偶半位空间，由于受到关卡结构的制约，它不能与两处蓝色的奇半位合成完整箱位。
图11、受限半位
以上分别证明了同性半位相斥、异性半位相吸，定理2得证。
三、举一些例子具体看看半位定理的应用。
1、关卡《石山之颠》打开后（如图12右侧）在B5和H2有两处半位空间，B5是奇半位，H2是偶半位。很显然，两处半位可以合成一个箱位，合成后的腾挪就轻松一些了。
图12、关卡《石山之颠》
2、《四海飘零》也是双半位关卡，但它们（B8和F8）都是偶半位，不能合成一个箱位。关卡右上角的结构必需1个完整箱位才能腾挪。理解了半位定理的朋友就会思考：再有一个奇半位就好了。如图13，我在关卡左下黄框内设置的4个目标点，推到位刚好腾出1处奇半位，这样就很明显了，这4个点要先填死。一旦确定这4个点要先填，自然就不会掉入B5木箱推到B3点的陷阱了。
图13、关卡《四海飘零》
3、第100期比赛关卡《百尺竿头》有个姊妹关叫《百尺无枝》，它的右侧也许会出现3处同性半位空间，如果不了解半位定理，可能会浪费很多时间用来合成箱位。见图14，《百尺无枝》的右侧独立关《百变右行》，可以很好地诠释同性半位相斥的定理。
图14、关卡《百尺无枝》和《百变右行》
由这三个小例子也可看出，半位定理的应用是很广泛的。运用这一定理来解第121期比赛关卡，更可以达到事半功倍的效果。
2017年6月21日初稿
2019年3月14日整理
附件: 14百尺无枝右侧变化.png (2019-3-29 13:34:01, 48.54 KB) / 下载次数 53附件: 13四海飘零.png (2019-3-29 13:33:52, 34.37 KB) / 下载次数 58附件: 12石山之巅.png (2019-3-29 13:33:40, 41.4 KB) / 下载次数 54附件: 11.png (2019-3-29 13:33:27, 13.79 KB) / 下载次数 58附件: 10.png (2019-3-29 13:33:16, 9.14 KB) / 下载次数 56附件: 9.png (2019-3-29 13:33:06, 11.92 KB) / 下载次数 56附件: 8.png (2019-3-29 13:32:57, 26.8 KB) / 下载次数 63附件: 7.png (2019-3-29 13:32:50, 33.36 KB) / 下载次数 57附件: 6.png (2019-3-29 13:32:39, 27.58 KB) / 下载次数 62附件: 5.png (2019-3-29 13:32:31, 25.89 KB) / 下载次数 73附件: 4.png (2019-3-29 13:32:20, 42.74 KB) / 下载次数 61附件: 3.png (2019-3-29 13:32:11, 30.85 KB) / 下载次数 60附件: 2.png (2019-3-29 13:31:50, 27.06 KB) / 下载次数 58附件: 1.png (2019-3-29 13:31:11, 38.31 KB) / 下载次数 61
| 欢迎光临 魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/) | Powered by Discuz! X2 |