九宫格密码盘

Aster CODE➤GEASS, GameのDay, 理宅异闻录 Leave a Comment

九宫格密码盘能形成很多有趣图案,我们来鉴赏一下,我们关心的是图案的密码强度,也就是密码的种类个数.

三阶似乎有点复杂,先来个二阶的,显然旋转重合不算同一种

$$\begin{array}{*{20}{c}}
A&B \\
C&D
\end{array}$$

所以选A开始,一步的有三个选择,两步有3×2中选择,三步有3×2×1种选择

一共$4 \times (3 + 3 \times 2 + 3 \times 2 \times 1) = 60$种可能性

把ABCD看做四个城市,假如一个星球上有n个城市,我要旅游,至少得去一个城市,去的城市不能重复,那么可能的旅游路线数目有这么多

$$\mathop \sum \limits_{k = 2}^n \frac{{n!}}{{\left( {n - k} \right)!}} = {\text{e}}\Gamma \left( {n + 1,1} \right) - (1 + n)$$

地球上著名城市大约是2000个左右,代入n=1999(原谅我强迫症)得到一个5733位数,So,求出其中最短的路径有点困难,看看机票价格贪心算法也够了,这注定是个有生之年系列.


接下来上正菜,三阶的问题.这不简单嘛,改成9个点,去掉非法路径,取剩下的数量不就对了嘛.简单的DFS.算出来是766752个,So easy.然而这是错的.因为规则是动态变化的,2被取了那么1-3就能连了,规则还在不断变化.我去,怎么这么烦啊.(ToT)/~~~

咋办呢,行动方式分为竖步,横步,斜步和马步,分别判定可行性,然后累加进状态,行动后传递一个新的图案.好了,贴代码.嗯,我貌似无视了至少要四个点,你们也貌似无视了这个小bug就行.

(4.84 secs, 1,926,690,136 bytes)还不错.

网上查了下顾森大大早就解决过这个问题了,我帮你们把代码抄一下.

输出结果是986400, 389488, {56, 320, 1624, 7152, 26016, 72912, 140704, 140704},只有不到40%的原始遍历数据是有效的.

(把这玩意扔进OEIS,发现这叫A163889,我觉得我应该给他们投稿.)


接下来解决四阶的问题,首先操作有竖,斜0,到斜3,但是有了双重判定问题,Haskell代码不想改了,构造一下很绕的,Mathematica代码大修应该还可以用.

Shift+Enter,跑了半天没跑出来,我去吃了个饭还没跑出来,什么鬼.我算了下原始输入,噗,一算吓一跳,一共56874039553199个原始输入,这是爆内存虐CPU、GPU核爆的节奏啊!

算了,研究个简单点的问题,只能移动到临位的遍历问题,只能竖,斜0和斜1.也就是国际象棋King的遍历问题,呃,所以还有Queen遍历、Bishop遍历(更新:也不是不能定义.)、Knight遍历、Rook遍历、Pawn遍历(Pawn遍历和Queen遍历本质上是一样的).被研究的比较多的是Knight遍历.其中特殊的一类收尾相连的叫做遍历回路问题,或者周游问题.

本质上周游问题就是哈密顿圈问题,所以一般化算法就是把它整成图.找一条路径超简单,回溯法就行,到底有多少条路径很有难度,还没有考虑旋转重合,镜面重合之类的,引入了群论就要把自己绕进去了.懒得编程呢,就用Mathematica算一下King遍历回路的数目吧.

三阶King等价于图(这不就是划斜线嘛),16条遍历回路.

三阶Rook等价于图(有种平衡的美感),48条遍历回路.

三阶Queen等价于图(为啥我开了边对称优先还是感觉很变扭,难道这是四维空间的对称性?),1292条遍历回路.

来做几道数列题,n阶king图要输入多少个关系?一共(n-1)^2个方框,每个框6条线,其中内部的线被算了两次,减掉就行了.

$$Kn = {(n - 1)^2} \times 6 - {(n - 1)^2}$$

k阶Rook图呢?每个点都和其他2(n-1)个点相连,一共有n^2个点,但是连线被计算了两次

${R_n} = (n - 1){n^2}$

k阶Queen图比较复杂,可以逐行扫描,第一行每个点都是3(n-1)条连线,横线被重复算了两次,第二行(n-1)+2(n-2)条,横线同样被算了两次.....

最终结果是${a_n} = \frac{1}{3}n(n - 1)(5n - 1)$,(更新:有趣的是这正好是n×n的棋盘内放入两个可以互相攻击的皇后的方法数.)

标准棋盘8阶,关系一个个手打还不得累死我啊,有空再研究下一般规律吧.

(更新:Wolfram数据库里真的有,不用手输了,如此的话只有Pawn遍历有待解决了,因为Pawn图是和初始点有关的,没法一般化.)


初步估计上面这玩意最多只有10^42种可能性.


题图为4阶Rook图....这玩意儿真的不是LHC的远房亲戚...

发表评论