前苏联卫国战争时期,为了对抗德国纳粹,传递秘密情报,红军们发明了一种“秘密天窗”进行加密。虽然在今天的电脑技术面前,这种加密手段几乎是不堪一击,但进行这种加密解密不需要电脑的参与,只需要一张纸,一支笔,一张硬纸片,一把剪刀就可以进行,非常方便。用来写写日记,或挚友之间写点儿小秘密什么的还是非常实用的。还是先看一个例子吧:
左边格子里写的是什么?能看明白吗?在不知底细的人眼里,这只是一堆胡言乱语而已。现在,我们点“选择页码”,在下拉列表中选“1”,把“秘密天窗”覆盖到这张秘密电码上。原来是莫文蔚的《北极光》的歌词,呵呵,看到了吧?看完了第一页后,在下拉列表中选“2”,将天窗顺时针方向旋转90度,就能看到第2页。继续顺时针旋转天窗,就能看到第3页,第4页。呵呵,好玩吧?试试看吧!
那么,这个天窗是怎样制作出来的呢?
请观察右图:
容易看出,左上角标有“1”的格子,顺时针旋转90度后,刚好覆盖在右上角的“1”上。又旋转90度,就覆盖在右下角的“1”上。再旋转90度,又能覆盖在左下角的“1”上。其它数字也一样,旋转90度后将覆盖在相同号码的格子上。大家一定想到了,要加工一个秘密天窗,只要在在四个“1”中挑一个挖掉,在四个“2”中挑一个挖掉,四个“3”中挑一个挖掉……以此类推,在2n×2n的格子中挖去n×n个孔,就能加工出一个秘密天窗了。
果真如此吗?不完全是。事实上,我们还得考虑两个问题。
第一,孔与孔之间不能相连。如果两个孔连在一起,写信的时候这里将有可能会暴露出一整个词。暴露的词多了,很容易被别人猜出天窗的形状。极端的情况,假如我们所有的孔都在左上角这个区挖,那这个天窗可就完全没有意义了。因此,我们必须防止孔与孔连在一起。
第二,看左图这种情况。这个天窗中并没有相连的孔,而且也完全符合“旋转四次覆盖整个平面”的原则。但是,它只能存在于纸上,并不能制造出来。你哪张硬纸片照着它画下来剪一剪就会发现,碎了,咳咳……
要靠人力来完成秘密天窗,同时满足这两个条件还真不容易!幸亏我们有电脑,这下可好办了。第一个条件只需简单的判断就能完成,第二个条件似乎比较麻烦,但只要能看出这个问题等价于判断在图中某个位置使用“画图”的油漆桶工具染色,能不能一次把整个天窗染成同种颜色,也就不难构思出算法了。
判断天窗可不可用的问题已经解决了,那怎样找出一个可用的天窗呢?如果看过“八皇后”算法,相信这个问题绝对难不倒你。没错,一个典型的使用回搠的深度优先搜索问题。
现在能写出自己的天窗生成器了吧?不妨下载一份我写的看看,呵呵。