一类灵感来自稻妻解谜的谜题的通用解法

经过抽象并推广的谜题模型

谜题

\(a_1,a_2,\cdots,a_n\)是整数变量(模\(m\)剩余类)。\(P_1,P_2,\cdots,P_k\)\(k\)个操作,操作\(P_i\)使\(a_1,a_2,\cdots,a_n\)数值分别增加\(P_{i1},P_{i2},\cdots,P_{in}.\quad(i=1,2,\cdots,k)\) (模\(m\)意义下)

给定\(a_1,a_2,\cdots,a_n\)的初始值,试求有限的操作序列使\(a_1,a_2,\cdots,a_n\)变为同一个数。(模\(m\)意义下)

解法

由加法交换律,操作的顺序并不影响结果。设\(P_1,P_2,\cdots,P_k\)分别进行了\(x_1,x_2,\cdots,x_k\)次,则\(a_1,a_2,\cdots,a_n\)变为\(a_1+x_1P_{11}+x_2P_{21}+\cdots+x_kP_{k1},a_2+x_1P_{12}+x_2P_{22}+\cdots+x_kP_{k2},\cdots,a_n+x_1P_{1n}+x_2P_{2n}+\cdots+x_kP_{kn}\)

\[S'=S+PX\]

其中 \(S'=\begin{bmatrix} a_1' \\a_2' \\\vdots \\a_n' \end{bmatrix},\) \(S=\begin{bmatrix} a_1 \\a_2 \\\vdots \\a_n \end{bmatrix},\) \(X=\begin{bmatrix} x_1 \\x_2 \\\vdots \\x_n \end{bmatrix},\) 不妨将操作\(P_i\)记为向量 \(\begin{bmatrix} P_{i1} \\P_{i2} \\\vdots \\P_{in} \end{bmatrix}\)\(P=\begin{bmatrix}P_1&P_2&\cdots&P_k\end{bmatrix}\)

变形得到

\[PX=S'-S\]

这是一个模\(m\)意义下的线性方程组。我们只要给出一个解就解决了问题。

如果\(m\)为质数,则除\([0]\)以外都有数论倒数。任取符合要求(即所有数相等)的\(S',\)使用高斯消元法即可解决问题。

\(m\)为质数的幂时,设\(m=p^t\),作高斯消元法,当进行到某一列时,若对角线元素无数论倒数(即有因子\(p\)),则在下方将被消除的元素中找到与\(p\)互质的元素,两者所在两行交换,便可正常进行消元。若所有将被消除 的元素中均是\(p\)的倍数,则选取因子\(p\)的次数最小的元素与原来的对角线元素所在两行对换,消元可正常进行。

\(m\)为一般合数时,分解为不同质数的幂相乘的形式,分别改写成模不同质数的幂的线性方程组的形式并解之,最后用中国剩余定理合并解即可。

\(m\)不为质数的情况任选\(S'\)可能无解,因此需要枚举\(O(m)\)\(S'\)来寻找解。若\(m\)较大,计算上建议记录高斯消元法的步骤(表示为左乘原系数矩阵的矩阵)。

应用于原神解谜

原神中相关谜题之于上述模型是特例中的特例,虽然简单但也正是这些谜题引出了上述问题与思考。

如图谜题,即对其中某一方块,攻击之可改变自己和其余方块上的数字(以模\(3\)加法的形式),原神中应该都具体为自己和相邻方块数字+1。解密目标为通过一连串攻击操作使所有方块数字相同。

游戏内另有一类解密与此方块相同,但攻击是改变朝向,目标为所有方块朝向一致,与上述数字型解密内核相同。数字型是模\(3,\)朝向型是模\(4,\)\(m=3\)\(4\)

对于有\(n\)个方块的谜题,\(n\)个方块上现有的数字即为\(S.\ n\)个方块正对应\(n\)个操作,可按照操作的影响写出矩阵\(P.\)解方程组得到答案。

以图中谜题为例, \(P=\begin{bmatrix} 1&1&0&0&0 \\1&1&1&0&0 \\0&1&1&1&0 \\0&0&1&1&1 \\0&0&0&1&1 \end{bmatrix},\) \(S=\begin{bmatrix} 1 \\1 \\2 \\1 \\1 \end{bmatrix},\) 此处模数\(3\)为质数,故\(S'\)可任取,这里取 \(S'=\begin{bmatrix} 0 \\0 \\0 \\0 \\0 \end{bmatrix}.\)

得到方程 \(\begin{bmatrix} 1&1&0&0&0 \\1&1&1&0&0 \\0&1&1&1&0 \\0&0&1&1&1 \\0&0&0&1&1 \end{bmatrix} \begin{bmatrix} x_1 \\x_2 \\x_3 \\x_4 \\x_5 \end{bmatrix}\equiv \begin{bmatrix} 2 \\2 \\1 \\2 \\2 \end{bmatrix} \pmod 3\)

给出一个解:\(X=(2,0,0,1,1)^T,\)即攻击最左边的方块两次,最右边的两个方块分别一次即可。