二维码推箱子关卡 – 纠错码的别出心裁的应用

 

本文地址:http://sokoban.ws/blog/?p=4392

为了庆祝比赛十周年,20603先生在122期为比赛设计的《十年树木》关卡。我在博文中借此谈了一下“十年树木,百年树人”的出处

而在之前的121期,20603先生则为比赛设计了两个二维码关卡《推箱之家》和《推箱驿站》,并为此设计专门的皮肤。此两关若使用专门为二维码设计的皮肤,可以直接扫一扫打开比赛网站。

赛后,20603先生又放出了用于关卡设计的原始二维码,并指出了最后的关卡对原始的二维码作了改动。主关的原始二维码如下:

之所以可以改动二维码,其原因是二维码利用了一种可纠错编码 Reed-Solomon 码来进行编码。

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

另外五处刚好改变了5个格子(黑变白,或白变黑)。

根据二维码的标准,21×21规格的二维码一共有26个字节(Byte 一个字节8位,即8个黑白格),如下图:

邹兄设计的主关所用二维码采取的是有19个字节是记录真正的数据(实际上此二维码的内容,即网址 http://sokoban.ws 一共17个字节,加上字符串长度等额外信息,刚好用完19个字节)。

另外7个字节是用于纠错,能够发现和纠正3个字节的错误。二维码用的是 Reed-Solomon 纠错码。

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

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

此外,在邹先生的提议下,我们颁发了比赛十周年纪念奖。邹先生为此又额外设计或发布了几个二维码关卡,其中一个用于作为荣誉证书的“章”,另外两个印刷成不干胶贴纸,随证书发放给十周年奖的获奖者。

 

 

 

此条目发表在 推箱子, 数学 分类目录。将固定链接加入收藏夹。