数字魔方

mathe

其实我们不需要限定输入数据为1~$n^2$, 而且模也不一定需要选择为$n^2$.
可以改为任意模，这样就可以变成关灯问题的一种扩展了。其中关灯问题限定了模为2。

小铃铛

尽量减少记忆，1,3,5,7,9位取最大数字点定，剩下4个边块，按“T”字三个端点点击：
1.要求“T”字的一横的两个端点数字相同
2.每个端点的点击次数=把“T”字的交点数字点击成端点数字的次数

mathe

我们可以把问题扩展为对于一个$m\times n$的棋盘，每个格子里面有一个$0～M-1$的数字，每次操作可以将一个格子以及它相邻的所有格子中数据关于模M加一，目标是经过若干次操作后使得所有格子中的数据相等（或等于指定的数字）。
如果假设$M=p_1^{a_1}p_2^{a_2}\cdots p_t^{a_t}$,
我们可以
i)寻找出方案使得格子中所有数关于模$p_t^{a_t}$同余。
ii)寻找出方案使得i)变换后的结果再关于模$p_{t-1}^{a_{t-1}}$同余，并且将其中每个步骤重复$h_t$次，其中$h_t$是$p_t^{a_t}$的倍数并且除以$p_{t-1}^{a_{t-1}}$的余数为1. 于是经过这个替换后的步骤，所有的格子中数关于模$p_{t-1}^{a_{t-1}}p_t^{a_t}$同余.
依次类推下去，最终我们可以找到关于模$M$同余的变换方案。

所以上面的方案说明，是否存在关于模M的解，等价于是否对于所有的模$p_i^{a_i}$解都存在。

mathe

现在我们分析模$M=p^a$的情况
如同34#，将T看成是$m\times m$的分块矩阵，每个分块是$n\times n$的小方阵。
假设有$mn$维向量\(x=\begin{pmatrix}x_1\\x_2\\\vdots\\x_m\end{pmatrix}, y=\begin{pmatrix}y_1\\y_2\\\vdots\\y_m\end{pmatrix}\)使得$Tx=y$,其中每个$x_i,y_i$都是n维向量。
另外记n维向量$x_0=x_{m+1}=0$,于是我们有$x_{k+1}+Dx_k+x_{k-1}=y_k, 1\le k\le m$
设$g_m(2x)$为m阶第二类切比雪夫多项式。
于是$x_2=y_1-Dx_1=g_0(D)y_1-g_1(D)x_1, x_3=y_2-Dx_2-x_1=y_2-Dy_1+(D^2-I)x_1=g_0(D)y_2-g_1(D)y_1+g_2(D)x_1, x_4=y_3-Dx_3-x_2=y_3-Dy_2+(D^2-I)y_1-(D^3-2D)x_1=g_0(D)y_3-g_1(D)y_2+g_2(D)y_1-g_3(D)x_1,...$
最终我们需要$0=x_{m+1}=g_0(D)y_m-g_1(D)y_{m-1}+...+(-1)^{m-1} g_{m-1}(D)y_1 +(-1)^m g_m(D)x_1$
于是我们知道，只要模$M$情况求出方程$g_m(D)x_1=g_{m-1}(D)y_1-g_{m-2}(D)y_2+...+(-1)^m g_0(D)y_m$中$x_1$的任意一个解，就可以依次计算出$x_2,x_3,...,x_m$.而且这也是原方程是否有解的充分必要条件。
链接https://blog.csdn.net/mathe/article/details/1143634 中给出了M=2时这个过程对应的算法。
所以现在问题归结为在模$M=p^a$下对n阶方程$H x_1=b$的求解过程,$H=g_m(D), b=g_{m-1}(D)y_1-g_{m-2}(D)y_2+...+(-1)^m g_0(D)y_m$。
可以如下计算
i) 寻找矩阵H中p次数最少的一个元素，通过行列交换，使得这个元素被交换到第一行第一列，
ii）将第一行乘上常数使得第一行第二列变成p的幂(模M的结果，包含$p^0=1$)。
iii)将第2~n行依次减去第一行的倍数使得它们第一列都是0.
iv)假设H中前k行消元过程都已经完成，这时前k列是对角线都是p的幂的上三角阵，而且含p的次幂依次不减
    在后n-k行后n-k列中找出含p的次数最少的元素，通过行列交换将这个元素交换到第k+1行k+1列的位置。
v)将第k+1行乘上常数使得第k+1行第k+1列变成p的幂(模M的结果，包含$p^0=1$)
vi)将第k+2~n行依次减去第k+1行的倍数使得它们第k+1列都是0.
vii)如果k+1<n,将k设为k+1,转到第iv)步继续，知道k+1=n,即所有行消元完成
最后我们将H变换为一个上三角阵$\bar{H}\bar{x}=\bar{b}$，对角线元素$h_1,h_2,...,h_n$全部是p的次幂而且次数依次不减。
于是这个方程有解的充分必要条件为$h_i | \bar{b}_i$, （其中$h_i=0$要求$\bar{b}_i=0$)。
而且如果$h_i=p^{u_i}$,（如果$h_i=1 <=> u_i=0$, 而如果$h_i=0=M=p^a <=> u_i=a$, 且$u_0\le u_1 \le u_2 \le \cdots \le u_n$)
那么方程的解的数目为$\prod_{i=1}^n h_i=p^{u_1+u_2+...+u_n}$

而如果M是更加一般的情况，对各个素因子依次求解判断，有解的充分必要条件是对每个素因子的幂都有解，而解的总数目就是各个素因子幂的解的数目的乘积。

小铃铛

后面发的第三题只要14步就可以完成9个1了：

mathe

小铃铛 发表于 2021-1-17 14:04
后面发的第三题只要14步就可以完成9个1了：

./findm9 933778566
Input:
9 3 3
7 7 8
5 6 6
Best move time 14
Candidate move:
Increase (1,2)
1 4 4
7 8 8
5 6 6
Increase (1,2)
2 5 5
7 9 8
5 6 6
Increase (1,2)
3 6 6
7 1 8
5 6 6
Increase (1,2)
4 7 7
7 2 8
5 6 6
Increase (1,2)
5 8 8
7 3 8
5 6 6
Increase (1,2)
6 9 9
7 4 8
5 6 6
Increase (1,2)
7 1 1
7 5 8
5 6 6
Increase (2,1)
8 1 1
8 6 8
6 6 6
Increase (2,1)
9 1 1
9 7 8
7 6 6
Increase (2,1)
1 1 1
1 8 8
8 6 6
Increase (3,2)
1 1 1
1 9 8
9 7 7
Increase (3,2)
1 1 1
1 1 8
1 8 8
Increase (3,3)
1 1 1
1 1 9
1 9 9
Increase (3,3)
1 1 1
1 1 1
1 1 1

小铃铛

中心块有数对的，貌似都需要步数25+

mathe

统计所有1-9各使用一次的情况
最少9次，最多35次:
cc[9]=504
cc[10]=360
cc[11]=216
cc[12]=864
cc[13]=1224
cc[14]=3528
cc[15]=4608
cc[16]=5184
cc[17]=8136
cc[18]=12600
cc[19]=16488
cc[20]=19008
cc[21]=24336
cc[22]=25920
cc[23]=33120
cc[24]=35712
cc[25]=34416
cc[26]=35136
cc[27]=29448
cc[28]=22752
cc[29]=20160
cc[30]=14040
cc[31]=6984
cc[32]=5400
cc[33]=2016
cc[34]=576
cc[35]=144

mathe

采用任意模以后，31#的性质就不一定成立了。
比如$2\times 2$的方阵，模3就不能把所有数字同步加1.
同样，$8\times 8$, $14\times 14$的方阵也不行
mbulb.zip (3.92 KB, 下载次数: 0)

2021-1-18 09:50 上传

点击文件名下载附件

附件中代码，有多种输入格式
i)
./mbulb MOD n
会使用模MOD, 对一个n*n的方阵，给出将全0变为全1需要的方案（如果存在，任给一个）
./mbulb MOD n m
会使用模MOD, 对一个n*m的矩阵，给出将全0变为全1需要的方案（如果存在，任给一个）
./mbulb filename
会从文件filename里面读数据，假设第一行为MOD n m, 然后后面n行，每行m个数，每个数0~MOD-1之间，给出将全0变为这个结果需要的方案

aimisiyou

关灯游戏升级版。