网格染色问题

mathe

红+黄=黄+绿 →　红=绿

用`n_i`表示相应编号格的数字（涂黑=1，留白=0）. 易得每一行加权和约束 \[n_1+2\*n_2+3\*n_3+4\*n_4+4\*n_5+3\*n_6+2\*n_7+n8=h\]`h`等于4×5矩形中数目和。
由于行数刚好足够，可知中间各行也满足这个约束。

显然，`h<4`时，`n_4=n_5=0`, 即中间两格为白，各行皆然，故中间两列为白，整列的加权和为零，所以`h<4`时无解。

mathe

而对于和为3，利用上面的结论，也比较容易分析出无解。
（已由上贴统一解决，删除）

mathe

和为6的情况比较复杂
我们查看上图红色和黄色部分构图，由于和为6，对于黄色所在行，四格加权系数分别为3，4，4，3.所以四格中最多两个黑格。
所以红色部分至少4个黑格。
而如果红色部分正好4个黑格，那么黄色部分需要正好两个黑格，于是只能n11,n14是黑格。同理类推，这时n18,n42,n51,n54,n23,n47也都是黑格。
而n11和n51都是黑格，说明它们所在行加权和为6只能是n3,n11,n51,n59是黑格，而n19,n27,n35,n43都是白格。
同样得出n20,n21,n22,n30,n38,n44,n45,n46都是白格。于是红色部分只有n28,n29,n36,n37可能是黑格，但是它们不能同时是黑格，同红色部分四个黑格矛盾。

所以红色部分至少5个黑格。下面我们需要穷举红色部分至少5个黑格的情况（还要满足各行加权和不超过6），总共应该只有5种，我们然后需要一一分析，应该可行

mathe

中心4×4不少于4个黑格（下图染成红色）去除对称情况应该只有一下5种（满足每行加权和不超过6）


要求n11+n12+14=1,n13=0，n3+n4+n6=1,n5=0,n51+n52+n54=1,n53=0,n59+n60+n62=1,n61=0
于是第3,4,6列共使用4个黑格，已用加权都为4，所以必然一列使用两个权为1的格子，另外两列使用权为2的格子，暂时无法淘汰，需要进一步分析


这个图要求n12+n13=1,n11+n14=0,n4+n5=2,n3+n6=0, 其中条件n4+n5=2会导致所在行加权和大于6，矛盾，淘汰


这个图和下面一个图的分析类似，只是3，4，5列需要改为4，5，6列，同样不行


这个图要求n3+n4+n5=1,n6=0,n11+n12+n13=1,n14=0,n51+n52+n53=1,n54=0,n59+n60+n61=2,n62=0
于是第3,4,5列共5个黑格，而已使用加权和分别为3，4，4。由于余下格子加权系数都是1或2，所以只能第3列两个,使用2+1模式，第4，5列一个使用加权为2的格子，另一个使用加权为1的两个格子
也就是第一行和第八行至少有一行使用了两格（3，4，5列），它们在这两行的权为3或4而且至少有一个权为4，所以这一行加权和大于6，矛盾，所以淘汰


这个图要求n11+n12+n13+n14=0,n3+n4+n5+n6=2,所以n3=n6=1,n4=n5=0,然后第三列加权和大于6矛盾，所以直接淘汰。

mathe

上一页分析以后只有其中第一个图还有可能，其余的都已经淘汰。
而第一个图，其中3,4,5,6这四列只有如上图六种可能的分布.

现在以第一种情况为例子，我们查看前四行与2,3,4,5,6这五列构成的黄框矩形，由于3,4,5,6这四列所有黑格已经确定，用了4个黑格。
我们得出n2+n10+n18+n26=2. 由此，继续看前四行和前五列构成的绿框矩形可以得到n1+n9+n17+n25=1
另外我们在查看2,3,4,5行和2,3,4,5,6列构成的蓝框矩形，可以得出n10+n18+n26+n34=1, 并且继续看2,3,4,5行和前五列构成粉框矩形可以得到n9+n17+n25+n33=2
注意到n35和n38所在行中n35和n38的权重都是3，权重和已经是6，所以n33=n34=0
由此我们得出n1+n9+n17+n25=1, n9+n17+n25=2,矛盾。 所以第一种情况不可能。

同样第四种可以完成采用第一种相同的方法来淘汰。

而第三种和第五种，可以采用右边的矩形，即现查看前四行和3,4,5,6,7列的矩形，前四行和4,5,6,7,8列的矩形
2,3,4,5行和3,4,5,6,7列的矩形以及2,3,4,5行和4,5,6,7,8列的矩形，同样得出矛盾的情况而淘汰。

现在发现可以有更简单的淘汰方法
比如第二种，可以使用n1+n9+n17+n25=n6+n14+n22+n30=0, 也就是n1,n9,n17,n25全白。
但是n9+n17+n25+n33=n14+n22+n30+n38=1, 但是由于n35和n38在所在行权重均为3,n33=0,得出矛盾。

同样第六中，可以使用n8+n16+n24+n32=n3+n11+n19+n27=0
   n16+n24+n32+n40=n11+n19+n27+n35=1, 但是n40根据n35和n38所在行权重和已经是6，得出只能n40=0，同样矛盾淘汰。

所以所有的都已经淘汰，和为6时只能无解

mathe

9*9的情况也可以有类似的结果:

黑格数目	解总数目	本原解数目
1	0	0
2	0	0
3	0	0
4	120	23
5	24	6
6	0	0
7	0	0
8	2040	288
9	14	4
10	122	24

fc9.tgz (2.78 KB, 下载次数: 0)

2020-7-15 17:00 上传

点击文件名下载附件

10*10

黑格数目	解总数目	本原解数目
1	0	0
2	0	0
3	0	0
4	120	23
5	24	7
6	0	0
7	0	0
8	2040	288
9	4	2
10	108	24

fc10.tgz (2.85 KB, 下载次数: 1)

2020-7-15 17:46 上传

点击文件名下载附件

11*11

黑格数目	解总数目	本原解数目
1	0	0
2	0	0
3	0	0
4	120	23
5	24	6
6	0	0
7	0	0
8	2040	288
9	0	0
10	98	20

fc11.tgz (2.94 KB, 下载次数: 0)

2020-7-15 18:08 上传

点击文件名下载附件

hujunhua

有一个“对角格等和公式”，一时不知其用，一直未贴出。今天试了一下@mathe 在23#~25#的证明过程中应用，发现极其有效。

一个5×6（或者6×5)矩形的对角格之和相等。
如图：A1+F5=A5+F1, A1+E6=A6+E1。
推论：如果 A1=1, A5=0, 则F1=1,F5=0.（称为“长距复制”）
　　　或者 A1=1, A6=0, 则E1=1,E6=0.（称为“短距复制”）

就是这个推论很有效，直接将两已知格复制得到两未知格。
    Ａ  Ｂ Ｃ Ｄ Ｅ Ｆ
１&#11035;&#11036;&#11036;&#11036;&#11035;&#11035;
２&#11036;&#11036;&#11036;&#11036;&#11036;&#11036;
３&#11036;&#11036;&#11036;&#11036;&#11036;&#11036;
４&#11036;&#11036;&#11036;&#11036;&#11036;&#11036;
５&#11035;&#11036;&#11036;&#11036;&#11036;&#11035;
６&#11035;&#11036;&#11036;&#11036;&#11035;

mathe

很有用的方案，特别把8*8的解扩展成9*9直到更高阶应该可以用这方法

hujunhua

mathe 发表于 2020-7-15 16:59
9*9的情况也可以有类似的结果:

我曾以为

□ □ □ ■ ■ □ □ ■ □ □ ■ ■ □ □ ■ □ □ ■ ■ □ □ ■ □ ■ ■ ■ □ □ ■ □ ■ □ ■ □ □ ■ □ ■ □ ■ □ □ ■ □ ■ □ ■ □ □ ■ □ ■ □ ■ □ □ ■ □ ■ □ ■ □ □ ■	□ □ ■ ■ □ □ ■ □ □ ■ ■ □ □ ■ □ ■ ■ ■ □ □ ■ □ ■ □ ■ □ □ ■ □ ■ □ ■ □ □ ■ □ ■ □ ■ □ □ ■ □ ■ □ ■ □ □ ■ □ ■ □ ■ □ □ ■ □ ■ □ ■ □ □ ■ ■	■ □ ■ □ □ ■ ■ □ □ ■ □ ■ □ □ ■ ■ ■ □ ■ □ ■ □ □ ■ □ ■ □ ■ □ ■ □ □ □ □ ■ □ ■ □ ■ □ ■ □ □ ■ □ ■ □ ■ ■ ■ □ □ ■ □ ■ □ □ ■ ■ □ □ ■ □ ■
12#图2	13#图4	14#图2

是同一个无边界解的不同局部，结果发现只是一个45度方向无穷长带状解的不同局部，带在水平方向的宽度为19, 并不能扩展到整个平面。

这个带状区域最大可以框出一个10×10的正方形网格（下图左）。这与26#表3中“11*11正方形网格，9个黑格”对应解数为0是相符的。

“11*11正方形网格，9个黑格无解”解决了我未曾言说的问题：是否存在无边界解。11*11尚且无解，更大的就不谈了。

⬜⬜⬜⬛⬛⬜⬜⬛⬜⬛ ⬜⬜⬛⬛⬜⬜⬛⬜⬛⬜ ⬜⬛⬛⬜⬜⬛⬜⬛⬜⬛ ⬛⬛⬜⬜⬛⬜⬛⬜⬛⬜ ⬛⬜⬜⬛⬜⬛⬜⬛⬜⬜ ⬜⬜⬛⬜⬛⬜⬛⬜⬜⬛ ⬜⬛⬜⬛⬜⬛⬜⬜⬛⬛ ⬛⬜⬛⬜⬛⬜⬜⬛⬛⬜ ⬜⬛⬜⬛⬜⬜⬛⬛⬜⬜ ⬛⬜⬛⬜⬜⬛⬛⬜⬜⬜		⬜⬜⬜⬛⬛⬜⬜⬛⬜⬛ ⬜⬜⬛⬛⬜⬜⬛⬜⬛⬜ ⬜⬛⬛⬜⬜⬛⬜⬛⬜⬛ ⬛⬛⬜⬛⬜⬛⬜⬜⬛⬜ ⬛⬜⬜⬜⬛⬜⬛⬛⬜⬜ ⬜⬜⬛⬛⬜⬛⬜⬜⬜⬛ ⬜⬛⬜⬜⬛⬜⬛⬜⬛⬛ ⬛⬜⬛⬜⬛⬜⬜⬛⬛⬜ ⬜⬛⬜⬛⬜⬜⬛⬛⬜⬜ ⬛⬜⬛⬜⬜⬛⬛⬜⬜⬜
10×10网格9黑格		中心4×4旋转90o

hujunhua

引理   不可能出现&#11036;&#11036;&#11035;&#11036;&#11036;&#11035;&#11036;&#11036;的行。
　　即26#@mathe的加权方程\[n_1+2n_2+3n_3+4n_4+4n_5+3n_6+2n_7+n_8=6\]的一个解(0,0,1,0,0,1,0,0)实际不会出现。
　　因为这样的染色会通过27#的“短距复制”和“长距复制”产生链式反应，复制到所有行，这显然不是一个合格解。
推论：一行的中间四格`n_3+n_4+n_5+n_6<2`。
　　按加权方程，`n_3+n_4+n_5+n_6<3`是显然的，如果等于２的话，就是(0,0,1,0,0,1,0,0)，与引理相矛盾。

证明：假定存在一个6黑格解，那么它的中间４列的任何连续5行，按引理的推论每行黑格数最多为1, 于是整个5×4矩形框住的黑格数最多为5, 这与假设相矛盾。