包含24個正方形和24個等腰直角三角形的方形对称图案

ejsoon

ejsoon 发表于 2024-7-21 22:38
看來七方是一個待開發的領域。

是否可以考慮加上「外圍是一個大正方形、所有線段都要連成一片」的條件之 ...

我只要24條線以內的就可以了。不知你本次搜索的終極目標是多大？

目前有哪些剪枝條件？

mathe

E9.tgz (51.93 KB, 下载次数: 2)

2024-7-23 07:11 上传

点击文件名下载附件

30条边以内的，E型竟然只有一个，不过挺好看的

mathe

9*9格子的边数不超过50的也全部产生了，共7万多个结果，文件太大了，没法直接上传
E9.tgz (272.71 KB, 下载次数: 3)

2024-7-23 13:39 上传

点击文件名下载附件

不过可以通过这个附件的数据文件E9.out（仅包含这7万多个文件名）和里面附带的程序gen5.cpp恢复所有的图。
比如
g++ -O3 gen5.cpp -ogen5
./gen5 < E9.out

mathe

让gen5.cpp在调试状态下运行initrow函数然后输出内部数据，可以得到
(gdb) p rowsi
$1 = {{4, 3, 2, 1, 0, 1, 2, 3, 4}, {9, 8, 7, 6, 5, 6, 7, 8, 9}, {14, 13, 12, 11, 10, 11, 12, 13,
    14}, {19, 18, 17, 16, 15, 16, 17, 18, 19}, {24, 23, 22, 21, 20, 21, 22, 23, 24}, {24, 23, 22,
    21, 20, 21, 22, 23, 24}, {19, 18, 17, 16, 15, 16, 17, 18, 19}, {14, 13, 12, 11, 10, 11, 12,
    13, 14}, {9, 8, 7, 6, 5, 6, 7, 8, 9}, {4, 3, 2, 1, 0, 1, 2, 3, 4}}$
(gdb) p cxi
$2 = {{44, 43, 41, 38, -1, 28, 31, 33, 34}, {43, 42, 40, 37, -1, 27, 30, 32, 33}, {41, 40, 39, 36,
    -1, 26, 29, 30, 31}, {38, 37, 36, 35, -1, 25, 26, 27, 28}, {-1, -1, -1, -1, -1, -1, -1, -1,
    -1}, {28, 27, 26, 25, -1, 35, 36, 37, 38}, {31, 30, 29, 26, -1, 36, 39, 40, 41}, {33, 32, 30,
    27, -1, 37, 40, 42, 43}, {34, 33, 31, 28, -1, 38, 41, 43, 44}}$
1是对横向线段的编码，2是对从左下到右上方向小线段的编码。
左上角第一条横向小线段编码为4，也就是它如果出现，对应16进制输入数据第4比特（最低比特为0比特）为1，不然第4比特为0.
同样左上角第一个格子从左下到右上方斜向小线段编码为44，也就是最高比特为1时它出现，不然不出现。

hujunhua

我也打算编程计算一下，好久没有编程了，先拿7X7网格试试手，这是最小的奇数网格大小，编码是最简单的。

编码方案如下：
1、7x7的网格中只有A类图案，四个中心□是定死了的，剩下的格子边48条对称归并为6组（每组8条），可用一个6位二进数来编码，码位如下图所示（从高位到低位升序）。
2、斜线段用格子来代表，用三进制编码，0-不出现，1-斜率为1，2-斜率为-1。轴心格固定为0，不参与编码，剩下的36格对称归并为6组，所以编码是一个6位三进数，码位如下图所示，正好与上条的码位一样。

7X7码位

例如下面这个图案的编码就是001000.020112。可以压缩一下：2进制部分按3位分节化为2位8进数，3进制部分按2位分节化为3位9进制。本例编码就是10.215

001000.020112

hujunhua

按上述编码方案，共有2^6·3^6=6^6个编码。
搜索方法如下：
1、搜索2^6个编码的纵横线图案，标记所包含的水平□数（不包括4个中心格），分为□20, □16, □12, □8组等4组。
2、搜索3^6个编码的斜线图案，标记所包含的◇数，分为◇0，◇4，◇8，◇12等4组。同时剔除其中三角形超出24的编码。
3、搜索□20×◇0, □16×◇4, □12×◇8, □8×◇12交叉组，找出三角形刚好24个的编码图案。

hujunhua

最小网格14X14. 已突破12X12。
斜置能减少覆盖的格点量数，但水平网格仍然是14X14。

14X14C16L48

斜置

hujunhua

最小网格18X18。斜置能减少覆盖的格点数量，但水平网格仍然是18X18。

hujunhua

从这个模型的标注看的出来，它有3个自由度。需要满足以下不等式：
c=3a+2k, k≥1, k≠a→c≠5a, d≥c+1=3a+2k+1.
取a=k=1的话，会使得c=5a, 所以d=≥3·1+2·2+1=8，网格最小16×16.
发现16×16确实可以取到，比上楼小 1 圈。
上楼取的是a=2, k=1, c=8, d=9.

自由度计算模型

hujunhua

               一、按中心正方形分类

如果总是让外面的那个大□水平放置，则16线图案一共有3种类型：
B：3正1斜，C：2正2斜，D：1正3斜。
由于线条必须从中心□的边延伸出来，斜线也不例外，于是必有◇，没有A型。
如果允许外面的大□斜置，那么D类就是B类中的◇最大的情况。

               二、20个偏置正方形的构成与分组

图案上线段分为两组——横竖组和双斜组。
□只能由同组线段形成。除去4个中心□，还需20个偏置□。
B类，20个偏置□全部由横竖线形成。
C类，20个偏置□两个线组按8+12分配。
D类，20个偏置□全部由斜线形成。
偏置□按对称等价可分为5组，每组4个。包括4个角组和一个中轴组。
【术语】（备方图）B类由横竖线、D类由斜线构好20个偏置□的图案。

【术语】（井字格）内外两个平行的同心□，内层□的四边两端向外延伸至外层□形成井字格。。
1个井字格能提供2个角组和4个单矩形。如果4个单矩形成为中轴组，这个井字格就称为【九宫格】。
即使是1个九宫格，也只能提供3个组。还差2组，故至少需要2个井字格。
3个井字格能提供6个角组。这已超编，显然不行。
所以，必须正好是 2 个井字格的配合，才可能恰好产生四角一中的五组偏置□。

比如 1 个九宫格与 1 个一般井字格组合，恰好能产生四角一中的五组。只要它俩的矩形不会再组合或者分割出一个中轴组就好。
或者2个一般井字格组合，已能提供4个角组。它俩的矩形可再组合或者分割成 1 个中轴组则正好。

对于B类和D类而言，这意味着三个同向□中必有一对不相交，即不构成井字格。
对于C类，这意味着两个方向必须各自相交，一个构成一般井字格，一个构成九宫格。
可见C类单纯一些，可以提前解决。B类和D类细分更多，需要仔细列方程和不等式。

                三、⊿的遍历和增减

数⊿要掌握方法，否则很容易数错。
无重无漏遍历的方法：先遍历直角顶点（十字线），对每个直角顶点，再遍历它的十字线交到的斜边。
【符号与缩略语】一个直角顶点 R 所关联的 ⊿ 数量记作⊿(R)。
【符号与缩略语】若正方形 A 的1个顶点所关联的⊿ 数量为 x, 则⊿(A)=4x，称为A所关联的⊿ 数量。
任一个直角顶点 R，⊿(R) 等于它的十字线所交到的斜线数量。
在R的十字线交到的斜线数量不变的情况下，影响 ⊿(R)的因素就是其中穿过它的斜线数量。
每多一条斜线穿过R，⊿(R)就减少一个。

                四、两个中心正方形的斜交

【定义1】A、B 两个中心正方形斜交，如果A的顶点在B的边的中点，就称A在B上。（见图2）
A在B上，则A的面积是B的一半。所以，两个斜交的正方形不可能彼此互在。

如果俩正方形的边都充分延长，彼此相交，那么彼之边都会被此之十字线交到，每个顶点（十字线）最多都能关联4⊿，故⊿(A)=⊿(B)=16，合起来32超过24。
减少的情况是A在B上（见定义1）。A的每个顶点都恰好被B的 1 条边穿过（只能是 1 条，2条的话就成为B的顶点了），所关联的 ⊿ 各减少1个，⊿(A)=12。
这时B不可能在A上，B的每个顶点还是关联4⊿，所以⊿(B)=16。⊿(A)+⊿(B)=28，仍然超过24.

可见，俩中心正方形的边充分延伸，彼此相交是不行的。必须收缩到只交于内环，见图1和图2.（图中未画出收缩后消失的外环，脑补一下）。
【不能过河】正方形(A)的两条平行边充分延伸，整个看起来像条河。收缩的结果就是 B 的一条边(d)只能与河的一边相交。这条规则就俗称“不能过河”。
否则，如果过河，在A的垂直于 d 的对角线镜像中，d仍然是d, A的河转过90度了。结果就是d与A的4条边都相交，回到了从前（充分延伸）。

由图1和图2可见，俩中心正方形斜交限于不过河时，只能产生4⊿或者8⊿，离编制还差很远，必须有更多的中心正方形相斜交。

                     五、一个正方形与一个井字格斜交


如图3，黑色□A和蓝色□B构成井字格AB（A外B内），红色正方形D与它斜交。D与A、B都相交，并保持都互不过河。
此即所谓“一个正方形与一个井字格斜交”。容易证明，一个合格的16线图案中必定包含这种子图案。

图3显示了◇D的一系列特殊位置——穿过井字格AB的直角点的位置。
【符号与缩略语】如果◇D处于位置◇1与◇2之间的开区间，就记作◇D∈(◇1, ◇2).
A和B的一些特殊的边长比会导致图中有些编号的位置重合，区间合并。
例如图4，左图是◇5与◇6重合，右图是◇3与◇6重合的情况，这都过了河。因为◇6就是一个要过B的河才能交到外环A的位置。
【符号与缩略语】井字格AB的直角点除了A和B的顶点，还包括B的延长边与A的交点，简称A与B的交点，一共8个，属于一个对称等价组，记作A×B。



下面来计数◇D在不同位置与井字格AB斜交时所能产生的 ⊿ 数量。

    case1 ◇D在◇6向外的任何开区间，◇D的每个顶点有2⊿ ，计8⊿；AB的每个直角点各有1⊿，计16⊿，合计24⊿。
这是没有三线共点，⊿无退化而最齐全的情况，其它D在边界上的情况在它的基础上都有所减少。
    case2  ◇D=◇1, ◇3, ◇4 or ◇5，都存在4个直角点被一条斜线穿过，⊿()=24-4=20。
    case3  ◇D=◇2，AXB的每个直角点被一条斜线穿过，⊿()=24-8=16。   
    case4  ◇D=◇3=◇4（◇3与◇4重合），◇D在□A上，□B在◇D上。□B、◇D的每个顶点被一条斜线穿过，⊿()=24-4-4=16。
   

                     六、B类的第3个水平正方形

B类的第3个水平正方形且记为C。
case1 已有24⊿，C与D不能再相交。
case2~4, 最多的有20⊿，还不够数，C与D必须相交。
但是 C 是必须与A、B之一形成井字格的，与D相交又会如上所述产生至少16个⊿，结果至少32⊿，超编。
所以，C不能与D再相交，16线图案只有case1一种斜交方式。

                      七、C类的第2个斜向正方形

C类的第2个斜向正方形，就是与D平行的那个，也记为C。
case1 已有24⊿，C与AB不能再相交。
case2~4, 最多的有20⊿，还不够数，C与AB必须相交，那么如上所述又会产生至少16⊿，结果至少32⊿，超编。
所以，C不能与AB再相交，16线图案只有case1 一种斜交方式。

                      八、16线图案的构造特征

     至此可以总结出16线图案的结构特征：
1）恰好包括一个正方形与一个井字格的斜交，这部分不与第四个中心正方形斜交
2）没有三线共点，
3）斜交的俩中心正方形互不“过河”，只相交于内环。

24#的那个图不符合2）,  所以是不正确的（那是我和ejsoon根据mathe的字符图给补绘的）。不存在6X6网格的16线图案。
16线图案的最小网格是10X10的，如下图所示。更多的16线图案待发。