魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 569|回复: 7

推箱子游戏中半位空间的奇偶属性与磁铁效应 [复制链接]

Rank: 3Rank: 3

积分
738
帖子
67
精华
2
UID
1316434
性别
保密
兴趣爱好
推箱

智力游戏设计大师 超级搬运工

发表于 2019-3-29 13:36:58 |显示全部楼层

推箱子游戏中半位空间的奇偶属性与磁铁效应

/ Zou Yongzhong

通常半个箱位是指占位2×2的小正方形,这里简称“半位”。为避免“2个半”的理解歧义,“2个半位”我在这里称之为“双半位”或“两处半位”。2018年9月12日我在讲关卡《二泉映月》的逻辑关系时,已经讲过半位空间的一些理论和腾挪要点,今天讲的应该算是两个定理吧,即关于半位空间的奇偶属性与磁铁效应,我称之为半位定理。这两个半位定理我在十多年前设计半位关卡时发现,前几年创作《失散之城》系列关卡以及比赛关卡《百尺竿头》时觉得有必要将其整理成文字。这次在第121期比赛关卡的设计中也运用了这个定理,所以现在把这篇文章整理发出来,相信更多人在看明白这个理论后能解开121期比赛关卡。

一、半位空间具有奇偶不变性。

1.png

图1 偶性半位和奇性半位

如图1,把半位空间左上格A对应的坐标横轴数字与竖轴数字相加,得到的数是偶数的,我称之为“偶性半位”或“偶半位”,反之,称之为“奇性半位”或“奇半位”。半位空间的坐标以左上角即A点的坐标来描述。通常横向坐标以字母标注,纵向坐标以数字标注,比如图1的F4半位是偶半位。但这篇文章为便于区分奇偶,部分横向坐标也以数字标注,F4半位标为6-4半位。定理1:在一个关卡地图内,一处半位空间不论移到关卡何处,其奇偶性不变!

证明:有多种方式可以证明这一定理。

1、首先,用图解的方式直接证明:


2.png

  图2、半位空间移动的几种常见情形

如图2,中间的小关卡正中是一个偶性半位空间,通过简单的变换,可以移动半位空间到6个不同位置。去除对称重复,我们分析下面图3的三种情形:

3.png

图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.png

图4、复杂和隐蔽的半位空间移动

如图4,半位空间从下方移到上方,似乎看不清中间过程,好像推了这几只箱子,半位空间突然就跳到上面去了,中间看不到半位空间的连续移动。其实,这种复杂的移动也可以分解成图3的简单情形。半位空间在移动过程中其位置处于待定状态,移动过程中虽然看不到半位空间,但每一步都会产生位置待定的半位空间,且任何待定状态都是图3的两种情形(平移和斜移)之一。每一步状态分解如下:

5.png

图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.png

图6、半位空间移动1格

3、我们用两种方法证明了“定理1”:在一个关卡地图内,一处半位空间不论移到关卡何处,其奇偶性不变!这个理论有广泛的应用,在此举一个例子,如图7:

7.png

图7、两个关卡的死活判断

如果告诉你这两关一死一活,怎么快速判断呢?掌握上述“定理1”后,这两个关卡孰死孰活就一目了然了。要安全移出D7木箱,就会产生C7半位空间,这个半位是偶半位。左侧关卡M3处有一偶半位,移到C7位就有了过关的可能;右侧关卡L3处有一奇半位,无法移到C7位,所以它必然是个死关。

二、双半位空间具有磁铁效应。

一个关卡地图内若有双半位或多半位空间,它们之间具有同性相斥、异性相吸的磁铁效应。定理2:在一个关卡地图内,如果两处半位可以移动到邻近位置,具有相同奇偶属性的双半位不能合成一个完整箱位,具有不同奇偶属性的双半位可以合成一个完整箱位。

证明:这个定理的证明比较容易,我们对同性半位和异性半位分别进行证明。

1、同性半位相斥的证明:

一个关卡地图内若有两处以上的半位空间,任意两处半位移到邻近位置有两种情形:(1)错位相连;(2)对齐相连(横向对齐与纵向对齐是等价的)。

若是错位相连,那么如图8,左侧2处半位,右侧3处半位,错位相连的状态下,在半位空间内任意空格寄存1只木箱,均会阻挡搬运工的通道,形成死锁。所以同性半位错位相连不能合成1个完整箱位。

8.png

图8、同性半位错位相连

若是对齐相连,那么如图9,D4和F4双偶半位相连,就形成2×4的空间,这是1.5个箱位,关卡地图内多出半个箱位,必然在别处产生死锁(F3木箱死锁)。

9.png

图9、同性半位对齐相连

综上所述,同性双半位相连,要么不能形成有效箱位,要么产生死锁。同性半位相斥得证。

2、异性半位相吸。

这个是不证自明的,通常意义上的一个完整箱位是2×3的空间,它本身就包含1处偶半位和1处奇半位,也可以说,常规意义的2×3箱位,就是由异性双半位合成的。如图10,D3木箱和F3木箱分别向左右各移一格,B2半位(偶半位)和G2半位(奇半位)就在中间连成了1个完整箱位。

10.png

图10:异性双半位连成1个箱位

“定理2”是说,具有不同奇偶属性的双半位“可以”合成一个完整箱位,并非必然合成一个完整箱位,所以只要找到1个例证,便已证明(其实常规情况下都是可以合成的)。这里需要注意的是:

(1)并非所有完整箱位,都是由异性双半位合成的。如图11的绿色方框,这个箱位并非由双半位合成。

(2)并非所有异性双半位都能合成1个完整箱位。如图11红色方框,这是偶半位空间,由于受到关卡结构的制约,它不能与两处蓝色的奇半位合成完整箱位。

11.png

图11、受限半位

以上分别证明了同性半位相斥、异性半位相吸,定理2得证。

三、举一些例子具体看看半位定理的应用。

1、关卡《石山之颠》打开后(如图12右侧)在B5和H2有两处半位空间,B5是奇半位,H2是偶半位。很显然,两处半位可以合成一个箱位,合成后的腾挪就轻松一些了。

12石山之巅.png

  图12、关卡《石山之颠》

2、《四海飘零》也是双半位关卡,但它们(B8和F8)都是偶半位,不能合成一个箱位。关卡右上角的结构必需1个完整箱位才能腾挪。理解了半位定理的朋友就会思考:再有一个奇半位就好了。如图13,我在关卡左下黄框内设置的4个目标点,推到位刚好腾出1处奇半位,这样就很明显了,这4个点要先填死。一旦确定这4个点要先填,自然就不会掉入B5木箱推到B3点的陷阱了。

13四海飘零.png

  图13、关卡《四海飘零》

3、第100期比赛关卡《百尺竿头》有个姊妹关叫《百尺无枝》,它的右侧也许会出现3处同性半位空间,如果不了解半位定理,可能会浪费很多时间用来合成箱位。见图14,《百尺无枝》的右侧独立关《百变右行》,可以很好地诠释同性半位相斥的定理。

14百尺无枝右侧变化.png

图14、关卡《百尺无枝》和《百变右行》

由这三个小例子也可看出,半位定理的应用是很广泛的。运用这一定理来解第121期比赛关卡,更可以达到事半功倍的效果。

2017621日初稿

2019314日整理

已有 3 人评分经验 收起 理由
cube_master + 20 精华!
anian + 20 谢谢03兄分享!
sokoban + 20 很给力!

总评分: 经验 + 60   查看全部评分

Rank: 7Rank: 7Rank: 7

积分
5046
帖子
3081
精华
18
UID
13140
性别

论坛建设奖 八年元老

发表于 2019-3-29 23:37:45 |显示全部楼层
感谢邹兄把这么精妙的理论整理出来!

使用道具 举报

Rank: 2

积分
267
帖子
213
精华
0
UID
1330478
性别
保密
居住地
珠海市
兴趣爱好
结构

两年元老 四年元老

发表于 2019-3-30 10:39:32 |显示全部楼层
不太了解推箱子,但是楼主写得很好

使用道具 举报

Rank: 1

积分
88
帖子
58
精华
0
UID
1329918
性别
保密
居住地
珠海市
兴趣爱好
结构

四年元老

发表于 2019-3-30 11:51:22 |显示全部楼层
楼主激起了我对推箱子的兴趣

使用道具 举报

Rank: 4

积分
1115
帖子
87
精华
0
UID
1333517
性别
保密
兴趣爱好
推箱

四年元老

发表于 2019-3-30 21:18:16 |显示全部楼层
感谢03大师分享!非常有价值的理论,学习了。
顺便贴一下《百尺无枝》和《百变右行》的xsb:
################
#---*---*----*.#
#-.*$#.$*-*#.-.#
#-#-.--.#$.$-$-#
#-#-*-#*#-.*-*-#
#-$.#-$..#$-.$-#
##$$$--*$.$.#$.#
#---#*-$---$.$$#
#-$#--***..$---#
#@*--.---*-*-.-#
################
Title: 百尺无枝
Author: Zou Yongzhong(20603)

#########
##----###
##-*#--##
##**----#
##----*.#
###**-$-#
#@--*#*-#
#--**-*-#
##--$-.-#
###-*---#
#########
Title: 百变右行
Author: Zou Yongzhong(20603)

使用道具 举报

积分
1
帖子
1
精华
0
UID
1349353
性别
保密
居住地
曲靖市
兴趣爱好
理论
发表于 2019-4-2 10:33:22 |显示全部楼层
小时候玩过,还有这么多的理论,好好研究下,兴趣又来了

使用道具 举报

红魔

管中窥豹

Rank: 4

积分
1517
帖子
933
精华
4
UID
802
性别

魔方破解专家 超级搬运工 十年元老

发表于 2019-4-3 16:31:09 |显示全部楼层
20603大师是什么职业?是数学家吗?这么厉害!!!

使用道具 举报

Rank: 4

积分
1707
帖子
347
精华
0
UID
1252561
性别

超级搬运工

发表于 2019-4-15 22:06:24 |显示全部楼层
受教了,但要领悟到还需要时间

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2019-6-27 16:30

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部