网格染色问题

mathe

最后，一行周期为m的倍数说明这mn个数之和是n的倍数。而周期为n需要和是m的倍数。由于和小于mn,不能同时是两者倍数。只能得出所有行的周期必然是m或n,对应数据和是n或m的倍数

mathe

所以现在对于原题，将8*8扩充到充分大时，由于m=5,n=4,那么必然只有和分别为5和4的倍数时才有解。
其中和为5，对应周期为4，所以要求构造4*4的子矩阵，每行每列都正好一个1，共4!=24种解（没有去除对称情况）,周期扩展即为合法解
其中和为4，对应周期为5，所以要求构造5*5的子矩阵，每行每列都正好一个1，共5!=120种解 ,周期扩展即为合法解
其中和为10，对应周期为4，所以要求构造4*4的子矩阵，每行每列都正好俩个1，共90种解 （A001499[4])，周期扩展即为合法解
其中和为8，对应周期为5，所以要求构造5*5的子矩阵，每行每列都正好俩个1，共2040种解 （A001499[5]),周期扩展即为合法解

hujunhua

mathe 发表于 2020-7-17 19:26
所以现在对于原题，将8*8扩充到充分大时，由于m=5,n=4,那么必然只有和分别为5和4的倍数时才有解。
其中和 ...

结果并不需要很大，对于m=5, n=4, h=7, 前进一步，到9×9就无解了。
手工证明这个无解是可行的，因为4+5=9, 正好可以把2个4×5和2个5×4矩形铺在9×9网格中，只露出中间一个格子。所以总的黑格数为4*7或者4*7+1， 这为证明带来了额外的好处。

证明路线：
1、加权和式2个，系数为{1,2,3,4,4,3,2,1,0; 7}和{0,1,2,3,4,4,3,2,1; 7}，两式加起来得{1,3,5,7,8,7,5,3,1; 14}，包含了一行的全部格子。
2、一行中可能的黑格分布是有限的，按合并的系数包括：
    1+5+7+1，1+5+5+3，1+3+7+3，1+8+5，3+8+3，7+7.
3、其中7+7即□□□■□■□□□, 这个能进行链式复制，复制链为5-1--6-2--7-3--8-4--9-5（成环了），所以不能有。剩下   
       1+5+7+1，1+5+5+3，1+3+7+3，1+8+5，3+8+3.
4、即一行只能有3-4个黑格，所以要么8*3+1*4=28，要么7*3+2*4=29, 也就是1+8+5与3+8+3总共至少要出现7行。
系数8即中间列，正反对应都不变，中间列上至少出现7个黑格，这与只能出现3~4个相矛盾。

mathe

还有11*11以上没有和为9的解。8*8和为4只有周期解。9*9和为5或8只有周期解。12*12和为10只有周期解

mathe

9*9和为5的现在分析起来也很容易，使用hujunhua的加权和，这时为{1,3,5,7,8,7,5,3,1; 10},
再联立{1,2,3,4,4,3,2,1,0; 5}, 可得每行只可能为
1+5+3+1：111000001 和101000011
1+8+1：100010001
5+5：001000100
7+3：010100000和000100010
其中模式111000001和010100000长配短配完全，可以链式复制到所有行，淘汰！只余下
101000011（模式1，非周期，4个1皆有短配，整行可长距复制）
100010001（模式2，周期4）
001000100（模式3，周期4）
000100010（模式4，周期4）
如果不使用模式1，其它模式都是以 4 为周期，所以结果是周期的。
如果使用模式1，在不同的轨道（下表中的行号组合）复制形成不同的初始局面，如下表1所示。
                       表1    模式1在各轨道形成的初始局面

行号	1-6	2-7	3-8	4-9	5
局面	101000011 ********* ********* ********* ********* 101000011 ********* ********* *********	********* 101000011 ********* ********* ********* ********* 101000011 ********* *********	********* ********* 101000011 ********* ********* ********* ********* 101000011 *********	********* ********* ********* 101000011 ********* ********* ********* ********* 101000011	********* ********* ********* ********* 101000011 ********* ********* ********* *********

在上表中每个局面取一个含1的列，就得到了9×9网格的4个长距复制轨道图。
按图索骏，得到各轨道图可匹配的模式范围，如表2
表2    轨道--模式匹配表

行的复制轨道	1-6 1****1***	2-7 *1****1**	3-8 **1****1*	4-9 ***1****1	5 ****1****
列的匹配模式	无	110000101	101000011	无	100010001

表中显示两条轨道无匹配模式，模式1不能呆在这些行。
其它3条轨道都有唯一匹配，这就可以将表1中的轨道图用匹配的模式来代替。
匹配的模式比轨道图的1更多，替代的结果使得多出的1将所在行复制为模式1.
这新复制的行自然是在表2中别的轨道上，把列又指向别的模式，这就矛盾了。
所以模式1不能呆在这种有唯一匹配的轨道上。
显然，这种轨道成为了所匹配的模式的特征。

但是所有的轨道都是这样的特征轨道，没有非周期模式的立足之道。
所以只有周期解。

mathe

有了上帖的铺垫 现在也能简明分析了。
使用加权和{1,3,5,7,8,7,5,3,1; 16}， 辅以{1,2,3,4,4,3,2,1,0; 8}检验，得到以下7种模式

1+8+7:  100011000, (周期5)
3+8+5:  010010100, (周期5)
1+3+8+3+1: 110010011（非周期解，5个1中长配4, 足可复制全行）
1+7+7+1: 100101001,(周期5)
1+3+7+5: 110001100,(周期5)
1+7+5+3: 100100110, （非周期解，4个1皆有长配, 可复制全行）
3+5+5+3: 011000110,(周期5)

由于两个非周期模式都是可短距复制的，仿上贴列出短距复制轨道和轨道--模式匹配表，见表1

行的复制轨道	1***1***1	*1***1***	**1***1**	***1***1*
列的匹配模式	110010011	110001100 011001001	011000110	001100011 100100110
双模式的交		*1*001*0*		*0*100*1*

              表1  9×9网格的短距复制轨道及模式匹配表
淘汰掉两个特征轨道，剩下的两个轨道是互为镜像的，研究其一即可。就选*1***1***（2--6）吧.
轨道*1***1***虽不能完全确定所在列的模式，但2个模式有3个同位0,可将轨道上的3个*替换为0,如下图所示：

轨 道	行取模式 100100110	列匹配双模式的交 *1*001*0*	行0**0**00* 配011001001
* 1 * * * 1 * * *	********* 100100110 ********* ********* ********* 100100110 ********* ********* *********	********* 100100110 ********* 0**0**00*（同位0） 0**0**00*（同位0） 100100110 ********* 0**0**00*（同位0） *********	********* 100100110 ********* 011001001 011001001 100100110 ********* 011001001 *********
	左 开始局面	中 　　进展１	右 　　进展２

同位0所在的3行以雏形 0**0**00* 只能匹配唯一的模式：011001001，是最初模式的镜像。
居然有3行(上图右)，但我们已明了其轨道长度为2, 明显不符。

至于模式110010011, 由同位零得到行的雏形00**0**00, 直接匹配不到模式。
所以，9×9和为8没有非周期解。

mathe

8*8和为4的情况，使用模式{1,2,3,4,4,3,2,1;4}只能有模式
4: 00010000
3+1: 10100000或10000100，模式10100000可以通过长短距复制任意扩展，所以需要淘汰
2+2: 01000010
2+1+1: 11000001可以通过长短距复制任意扩展，所以需要淘汰
即余下模式
00010000(P)
10000100(P)
01000010(P)
其中标志P表示周期5的模式。所以8*8和为4也只有周期解

mathe

前面都是使用模式证明某些方案不存在，说服力还不够强，现在我们来分析8*8和为5情况的所有解，由于周期解已经很清晰了，所以分析中会只需找非周期解:
8*8和为5的情况，使用模式{1,2,3,4,4,3,2,1;5}只能有模式
4+1: 10010000或00010001
3+2：01100000或01000100，前者可以通过长短距复制任意扩展，所以需要淘汰
3+1+1: 10100001
2+2+1: 11000010
即余下模式
10010000
00010001(P)
01000100(P)
10100001
11000010
其中标志P表示周期4的模式。
由于周期解我们已经很了解了，下面只寻找非周期解，
而三个非周期模式都可以通过短轴长距复制成自身模式，于是数字1在对应的列间隔四格（如果不越界也必然是1），


如果使用10100001，（注意到每列1****1**模式只有10000101),有
10100001
0*0****0
0*0****0
0*0****0
0*0****0
10100001
0*0****0
1*1****1 (这种导致最后一行还是只能10100001,于是长距复制第三行矛盾，淘汰）
或
********
10100001
0*0****0
0*0****0
0*0****0
0*0****0
10100001
********（第1，3，8列必然第一行和最后一行一个0另外一个1），而0*0****0只有模式01000100符合，导致第二列中间四个全1淘汰。
或
********
********
********
10100001
********
********
********
********
（对应1所在每列模式为10010000或00010001），所以可以转化为
********
0*0****0
0*0****0
10100001
0*0****0
0*0****0
0*0****0
********（其中0*0****0只有模式01000100符合，导致第二列中间三个连续1淘汰。）

所以模式 10100001被淘汰。

如果使用模式11000010，同样长距复制有
11000010
00****0*
00****0*
00****0*
00****0*
11000010
00****0*
11****1*(这种导致最后一行还是只能11000010,于是长距复制第三行矛盾，淘汰）
或
********
11000010
00****0*
00****0*
00****0*
00****0*
11000010
********（而00****0*只能匹配00001001或00010001，即000**001,导致最后一列四个连续1，不符合任何模式淘汰）
或
********
00****0*
00****0*
11000010
00****0*
00****0*
00****0*
********（而00****0*只能匹配00001001或00010001，即000**001,导致最后一列*110111*不符合任何模式淘汰）.

所以只余下非周期模式10010000，这时所有候选方案只有
10010000
00010001(P)
01000100(P)
这时候长距离复制的限制只余下
********
0**0****
0**0****
10010000
0**0****
0**0****
0**0****
********
而其中第1，4列的第1,8行只能各一个1一个0 （两列匹配模式10010000或00010001），但是两者的1不能在同一行，不然还是模式10010000，继续长距复制矛盾），所以转化为

0**1****
0**0****
0**0****
10010000
0**0****
0**0****
0**0****
1**0****
或
1**0****
0**0****
0**0****
10010000
0**0****
0**0****
0**0****
0**1****

（注意0**1****只能匹配00010001,1**0****只能匹配10001000),两者分别转化为
00010001
0**0****
0**0****
10010000
0**0****
0**0****
0**0****
10001000
或
10001000
0**0****
0**0****
10010000
0**0****
0**0****
0**0****
00010001
根据(列1**0***0只能匹配10001000)，(列0**0***1只能匹配00001001)，又转化为
00010001
0**0***0
0**0***0
10010000
0**0***1
0**0***0
0**0***0
10001000
或
10001000
0**0***0
0**0***0
10010000
0**0***1
0**0***0
0**0***0
00010001
根据(0**0***1只能匹配00001001)，又转化为
00010001
0**0***0
0**0***0
10010000
00001001
0**0***0
0**0***0
10001000
或
10001000
0**0***0
0**0***0
10010000
00001001
0**0***0
0**0***0
00010001

根据(列0**01**1只匹配00001001), (列1**01**0只匹配10001000)转化为
00010001
0**00**0
0**00**0
10010000
00001001
0**00**0
0**00**0
10001000
或
10001000
0**00**0
0**00**0
10010000
00001001
0**00**0
0**00**0
00010001
而余下的0**00**0只能匹配01000100或反向00100010,所以得到每两个相邻的**都只能是10或01，所以四个*构成的小正方形中都正好两个1
于是第二个模式中前四行前五列将有6个1而不是5个1淘汰。只余下
00010001
0**00**0
0**00**0
10010000
00001001
0**00**0
0**00**0
10001000
其中所有*构成正方形有两种不同的选择方案，选择第2,3,4,5,6行，第3,4,5,6列，得出第6行的3,6列两个*必然一个0一个1.
所以得出任意一个*的正方形方案确定后，余下的正方形方案也唯一确定，总共只有两组非周期解，即分别为
00010001
01000100
00100010
10010000
00001001
01000100
00100010
10001000
或
00010001
00100010
01000100
10010000
00001001
00100010
01000100
10001000

hujunhua

在12#发现中心变换时，不禁就在想是否还有其它简要的变换。
事实上，变换在任何两个图之间都存在，只是变换的作用范围不同而已。

对相近的两个0-1 图` G_1, G_2`, `G1-G2`包含` \{0，1，-1\}`3种数字，其中 0 占据的就是`G_1∩G_2`部分,  `1，-1`占据就是两图相异的部分。
把这相异部分取反色，就是变换`G_1←→G_2`.
相异部分越少，变换的作用对子就越多，越有提取出来的意义。中心变换（4格）是格子最少的变换，作用范围为5对。
格子较少的变换，还发现两种6格变换，一种9格变换，一种11格变换。

0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0 1  0  0 -1  0  1  0  0 -1 0  0  1  0 -1  0  0 0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0	0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0 0  1  0  0 -1  0  1  0 0 -1  0  0  1  0 -1  0 0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0
6格变换1 , 作用于3对间	6格变换2，作用于5对间
-1 0  0  0  1 -1  0  0   0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0 1  0  0  0 -1  1  0  0 -1 0  0  0  1 -1  0  0 0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0	1  0  0  0 -1  1  0  0 0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0 0  0  0 -1  1  0  0  0 -1 0  0  1  0 -1  0  0 1  0  0  0 -1  1  0  0 0  0  0  0  0  0  0  0 0  0  0  0  0  0  0  0
9格变换，作用于5对间	11格变换，作用于3对间

表中的作用范围指的是8x8网格，和为9.
我们知道周期解易得，非周期解不易，有了上述变换，就容易从周期解得到非周期解了。

chyanog

用Mathematica搜索一下，耗时不到0.2秒，计算结果和mathe的一样，108个去重后25个。大概思路是求解线性方程组后遍历25个变量，再逐步剪枝

1. Clear["`*"];
   
2. F[s_:"i",n_]:=Symbol[s<>IntegerString[n,10,2]]
   
3. mat=Partition[Table[F["x",i],{i,8^2}],8];
   
4. eqn=Total[#,2]==9&/@Flatten[Partition[mat,#,1]&/@{{4,5},{5,4}},2];
   
5. A=Solve[eqn,Integers,GeneratedParameters->F][[1,All,2,1]];
   
6. k=Length[Variables[A]];
   
7. cond=LogicalExpand[And@@Thread[0<=Complement[A,Variables[A]]<=1]];
   
8. iter=Table[{F[i+1],0,If[Select[cond,F[i]==Last@Sort@Cases[#,_Symbol,-1]&],Evaluate@Boole[i<k],-1]},{i,k}];
   
9. cf=Compile[{{i01,_Integer}},
   
10. Module[{B=Internal`Bag[Rest@{0}]},
    
11. Do[Internal`StuffBag[B,#,1],##2];
    
12. Internal`BagPart[B,All]
    
13. ],RuntimeAttributes->{Listable}
    
14. ]&[A,Sequence@@iter];
    
15. Length[ans=Join@@(Partition[Partition[#,8],8]&/@cf[{0,1}])]//AbsoluteTiming
    
16. 
    
17. (* 去重 *)
    
18. func=Sort@{#,Transpose[Reverse[#,2]],Reverse[#,{1,2}],Transpose[Reverse[#]],Transpose@Reverse[#,{1,2}],Transpose[#],Reverse[#],Reverse[#,2]}&;
    
19. Length[ans2=GatherBy[ans,func][[All,1]]]
    
20. MatrixForm/@ans2

复制代码

10.0后的版本可以用DeleteDuplicatesBy代替GatherBy