第一百二十一期 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

anian

可以看到了。   谢谢杨兄!     

sokoban

anian 发表于 2019-4-26 06:14
那些图片我也无法看到。  有时候可以看到一张， 但其它的都是无法。
建议杨兄修改贴加入那些照片。

已经编辑了，上传到论坛了，应该总能看见了。

anian

那些图片我也无法看到。  有时候可以看到一张， 但其它的都是无法。
建议杨兄修改贴加入那些照片。

sokoban

20603 发表于 2019-4-24 00:24
　　杨兄分析很专业！被扫码器无视的是O6点。

　　看了上面第8楼的贴子，插的5个图都是从新浪博客转来 ...

我这里5个图都能显示，也许是有时网速慢时就不显示。

20603

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

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

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

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

第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

anian

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

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

sokoban

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

文/Zou Yongzhong

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

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