第一百二十一期 MF8 推箱子比赛 (121st)

sokoban

比赛将于北京时间 2019年3月8日 下午2时开始，
                          2019年3月29日 下午2时结束。



比赛网站：http://sokoban.cn



实时答案提交情况：http://sokoban.cn/solution_table.php


比赛关卡（比赛开始后可见）: http://sokoban.ws/current_comp.php

sokoban

(For 121th competition)
Submissions ordered by submission time

提交解法一览表 (Submitted Solutions Table)
人数：1+4

顺序(Order)	时间(Time)	名号(ID)	步数(#Moves)	推数(#Pushes)
1	2019-03-08 19:25:48	cjcjc	1782	389

副关答案列表

顺序(Order)	时间(Time)	名号(ID)	步数(#Moves)	推数(#Pushes)
1	2019-03-08 16:30:18	cjcjc	2917	518
2	2019-03-12 13:28:02	一目了然	1811	406
3	2019-03-12 17:18:59	stopheart	5799	934
4	2019-03-27 12:15:52	XiBeiTianLang	1799	400
5	2019-03-28 11:18:43	一目了然	1749	388
6	2019-03-28 11:32:41	XiBeiTianLang	1727	374

20603

二维码皮肤7个.rar (44.7 KB, 下载次数: 13)

2019-3-8 16:48:10 上传

下载次数: 13
QR_skin

永恒的家

文/Zou Yongzhong


　　这次第121期的比赛关卡比较特殊，是以二维码图形做关卡。去年（2018年）9月，箱友“微风中的歌声”在群里提出能否用二维码图形做关卡，后来anian先生用QQ群二维码生成了一个35×35的关卡图形。我也因此做了几个不同的二维码关卡。我觉得35×35的关卡太大，所以在生成二维码时选用尽可能少的字符，采用最低的7%容错率，做出的关卡尺寸是23×23。要进行二维码识别必须换专用皮肤，这里提供几个皮肤供选择，有anian先生做的，也有我做的。其中皮肤QR_code_For Ysokoban_ZYZ_1.png可以在关卡初始状态或中间状态进行扫码识别，如果识别不出来，只能换别的QR皮肤，正确过关才能扫码识别。当然，也可用推箱快手的逆推功能直接识别。

　　这期的主关和副关都是比赛网站的二维码，故取名《推箱之家》和《推箱驿站》。家还是驿站，home或者hotel，对于每一个箱友是不同的，不管您把这里当成家还是驿站，都祝您玩得愉快！

　　家和驿站，其实两者分别不是太大，驿站是旅途中的家，家是人生的驿站。年轻时我漂泊在外，居无定所，很想有自己的家。多年之后买了间30几平米的小房，似乎有了家。但计划赶不上变化，小房要换大房，这个城市要换到那个城市，买的房也不能成为固定的家。回想半生数十载，不论是漂泊的驿站还是固定的家，尚无一处住所能够连续住满5年。倒是来到这个推箱子网站超过5年了，转眼间推箱比赛已近10年，我玩推箱子已23年，不论人生如何变迁，小小的仓库一直跟随，它倒像我永恒的家了。希望杨博士和几位版主，好好经营这个网站，让它成为推箱子的永恒之家。

　　23年前一不小心推开了“仓库世家”这扇窗，这一推直推到满头白发，地老天荒。有诗为证：

　　推开仓库一扇窗，
　　箱帘蒙尘鬓染霜。
　　驿动少年梦犹在，
　　站台匆匆步未央。
　　永在路途未停息，
　　恒之所系为一箱。
　　的知南墙无捷径，
　　家指北疆两相望。

　　你能否从这首藏头诗中看到对关卡路径的提示呢？

　　主关有些难度，但难点不多，多推敲推敲或许就能过关。副关完全没难度，大胆推就行了。等比赛结束我再来讲讲关卡的设计思路与过关要点。

　　2019年3月8日

cjcjc

1 2019-03-08 19:25:48 cjcjc CN 1782 389
1 2019-03-08 16:30:18 cjcjc CN 2917 518
感谢20603大师提供的精彩关卡！这两关可以说超级难了。。

anian

恭喜超级兄过关!    

sokoban

20603 发表于 2019-3-8 13:19
永恒的家

文/Zou Yongzhong

20603兄讲得真好。想想我也玩推箱子20年了，这里的确可以算是一个家园了。1999年刚上大学才真正开始接触互联网，那时候是通过20603兄的网站开始了解推箱子的广阔世界，我至今印象深刻的是03兄的网站有一个“他山之玉"的栏目，那里有很多不同的推箱子程序。没想到一晃就成了一项伴随了20年的业余爱好。

我总是幻想着anian兄什么时候回国，我们可以举办一次推箱子大会，我们这些天南地北的箱友可以见见面留个大合影，哈哈哈

anian

sokoban 发表于 2019-3-9 11:19
20603兄讲得真好。想想我也玩推箱子20年了，这里的确可以算是一个家园了。1999年刚上大学才真正开始接触互 ...

这个想法好!   如果回来的确应该见见面留个大合影。  

20603

第121期MF8推箱比赛关卡解析

文 / Zou Yongzhong

　　这期比赛的主关和副关都是二维码关卡。从二维码生成的关卡，目标点固定，且不能过多修改，修改后就无法准确扫描了。这给关卡设计带来很大考验。关卡内部目标点不均匀分布达200多个，只能在空白处加少量的墙，这样腾挪起来会很容易，所以不能用常规思路构思关卡。关卡内有大量集中的目标点，如果木箱分散放置，填上这些目标点后很容易制造大量空位，所以我选择将集中的目标点直接堆积木箱。这使得关卡看起来木箱挺多，其实一大半都不需要动，玩家可将这些木箱改编成墙，看起来就简洁多了。考虑到墙比较少的区域腾挪会相对简单，因此我把主关和副关的开局都弄成了半位腾挪，增加些麻烦。这里我只讲一些关键点，其它常规的部分还是留给玩家自己思考吧。
我刚刚发布了《推箱子游戏中半位空间的奇偶属性与磁铁效应》。看过这篇文章的，对关卡应该有比较清晰的认知了。
　　一、主关和副关的关键都是要寻找箱位，1个完整的箱位。先来看主关。



　　主关做简单的开局处理之后，会发现有1处Q15偶半位。如果填死U13点和V14点，还会产生1处T14偶半位。如何填死U13点和V14点？这些基本的半位腾挪我就不讲了，看懂我以前讲《二泉映月》时总结的半位理论，应该比较容易腾挪出来。还好，这一关你无须先填死U13点和V14点，很显然，根据半位理论，这两处偶半位是无法合成1个完整箱位的，你即使腾挪出来也不过是中了陷阱，白费劲。
关卡上方还有一处容易发现的半位空间，若填死J2点和M2点，会产生I3半位空间。可是这也是偶半位，即使你能千里迢迢把这几个半位空间移到一起，它们都无法合成1个完整箱位。
　　从哪儿寻找1个奇半位呢？这是关卡的关键点。如果能移走M11木箱，填死绿色圆圈内的5个目标点，就刚好产生1处I8奇半位。如图，关卡地图内三个黄色方框是比较容易发现的偶半位空间，一个白色方框是稍微隐蔽一些的奇半位空间。I3偶半位和I8奇半位，恰好合成1个完整箱位！
想明白这些，接下来的难点就是如何移走M11木箱了。有一个办法，就是利用I3偶半位，腾挪到需要的位置，把M11木箱置换出来。这部分腾挪比较难，我在这里给出最关键的一部分解答：
DDLLdLLLuULuuuuuluuuLLDDLLDlluuuuuuurrRlllddRUlddddddrruuuLrdddlluuRDldllUURDrdddddddlluuUUUURlddddddrruuuuuLrdddddlluuuuRlddddrruuuLulDlLuRdrrrdddllllUUddllUURDrdrrrruuullDDRdrUdRRULdlluluuruuuurrrrruurrdddrddddLLdLdLrururrdLruuulDruuuluuullddlldDRdRRR
　　你能看明白这部分解答的逻辑吗？如果能看明白，其余部分的腾挪应该不难。如果还不知道接下来该怎么推，就再提示一下：推到这时，I3偶半位被推到哪儿去了？如何利用这个待定的半位空间完成剩下的步骤？
　　合成1个完整箱位后，腾挪就简单多了，收尾略有一点难度。这些就留给玩家思考了。

　　二、再来分析一下副关。我是特意减了墙做容易些，但从比赛过程看，作为副关还是难了一点。



　　这个关卡的关键也是用异性双半位合成1个箱位。很多朋友被难住的原因，我想可能是中了陷阱。如图，很容易看出， D9是奇半位（白色方框），如果我们填死绿色圆圈内的目标点：
uuuuUUURRUUddDrRddRRurrUULLulLLrrrdrrUUUULLUllllllDurrdLurrrrrdDDuurrdLrdddddlldlluuURRlldddrruLU
　　这会产生J10和H16两处偶半位（黄色方框），这两处偶半位很有用，J10偶半位可以与D9奇半位合成1个完整箱位，H16偶半位可以帮助打通J20向右的通道。相信很多人尝试过类似开局，其实是中了陷阱。
　　这个陷阱对有些人比较深，对有些人也许很快否定。因为J10偶半位与D9奇半位合成1个完整箱位，还是要腾挪一下的，一旦合成了，就会中招久一点，如果合不了，会误以为此路不通，刚好出了陷阱。
　　其实这样合成1个箱位，会造成左上角无法收尾。为什么无法收尾？原因是，用来合成1个完整箱位的D9奇半位，它就在左上角区域，所以左上角收尾后这个D9奇半位就被“没收”了，少了这个奇半位，左上角就必须向下借位才能收尾，故绿色圆圈内的目标点不能填死，两处黄色的偶半位均不成立。
　　如果没有这两处黄色的偶半位，只能在别处寻找偶半位了。我们若从L10进入右侧，刚好可以形成一处偶半位：
rrrrUUUURRurrUUUUUULLUllllllDurrdLurrrrrdDllULrdrruulDrrrULdrRRdDDrdDlDDRDLuuuruuluurDluuURDulL
　　推L10木箱进入右侧的腾挪，需要对死锁有较好的认知。如图标示，蓝色的M9半位，刚好是偶半位。D9奇半位和M9偶半位，顺利合成1个完整箱位。
　　有了完整的箱位，接着就是理清关卡的结构和顺序。当然局部腾挪也有点难度。对于腾挪比较吃力的箱友，我并不反对你分割关卡用程序来解。这就好像允许考生在家里考试，就无法限制考生翻书和使用计算器。编关者能够做的是尽量增加程序解关的难度，而不是禁止别人用程序。腾挪的最难点在右下部分，提醒一下，我在右下设置了一部分半位腾挪，你如果能看出哪些步骤是半位腾挪，就知道如何应对了。这里的半位腾挪只是一小段，很快就可以通过填死木箱得到完整箱位了。半位腾挪除了要掌握一些规律和技巧外，熟能生巧也比较重要。

　　这期比赛的关卡就分析到这儿，只是分析了关键点，想要过关，还要费些时间腾挪。如果有箱友实在无法过关又想看答案，我可以发解答动画到QQ群里。

　　前面说副关特意减了墙，原版应该是这样：



#######################
#******* ** *  *******#
#*     * ..**.$.     *#
#* ***$*$* ***$.$*** *#
#* *** .$.$# .$. *** *#
#* *** .   #   . *** *#
#* $ $$*.*.$ *$*  $  *#
#*.*.*.* * * * .**.***#
#       $$.$** $$ $$  #
#**# *** # $.. $. .*.*#
# **.*  .  #  *****.$ #
#* * ***$# *$$** ** * #
#*.** * .* #  *     $ #
#* $ .$. * # .*$*** * #
#  $$ $ #*$# $$  . .* #
#***.*.*   *$ ***** . #
#* $   * .##.*. $ $ * #
#* *** *$*   *. *.*$*.#
#* *** . # *$ *$ .$. *#
#* ***$*$  # $..***   #
#*@    * .** ** * * $ #
#******* ** . *  **  *#
#######################         
Title: 推箱驿站进阶版
Author: Zou Yongzhong
Date: 20181005

　　最后，贴出两关的原始二维码，让大家看看我改动了哪些点：

      




2019.3.29

sokoban

20603 发表于 2019-3-29 13:57
第121期MF8推箱比赛关卡解析

文 / Zou Yongzhong

仔细对比了一下主关的二维码，有6个位置黑白发生变化（其中有一个大概会被扫码器无视）：




另外五处刚好改变了5个格子（黑变白，或白变黑）


根据二维码的标准，21x21规格的二维码一共有26个字节（Byte 一个字节8位，即8个黑白格），如下图：



邹兄设计的主关所用二维码采取的是有19个字节是记录真正的数据（实际上此二维码的内容，即网址 http://sokoban.ws 一共17个字节，加上字符串长度等额外信息，刚好用完19个字节）。
另外7个字节是用于纠错，能够发现和纠正3个字节的错误。二维码用的是 Reed-Solomon 纠错码。

按照上图26个字节的分布，几个黑白改动的地方分别属于3个字节，刚好达到这个（26，19）纠错码的纠错能力极限，还是能够正确地扫码打开我们的比赛主页。

给定了二维码设计推箱子关卡，这是难度非常高的“命题作文”，为了达到必要的难度，邹兄不得不改动二维码。但是二维码是用 Reed-Solomon 纠错码编码的，能够容许少数改动（错误）而还能正确解码。这算得上纠错码理论在推箱子中得到应用的一个非常妙的例子吧。

20603

sokoban 发表于 2019-4-21 09:25
仔细对比了一下主关的二维码，有6个位置黑白发生变化（其中有一个大概会被扫码器无视）：

　　杨兄分析很专业！被扫码器无视的是O6点。

　　看了上面第8楼的贴子，插的5个图都是从新浪博客转来的，好像有两个图突然不显示了。