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

ejsoon

mathe 发表于 2024-7-21 06:41
试了一下让计算机先预填4个正向正方形，搜索所有的A型图案，对于8*8很快就可以结束。
但是处理10*10，在笔 ...

我懷疑需要借鑑多聯骨牌的算法。

我曾經做過一個python破解3D pentomino（五聯骨牌），跑某個圖形，半天才出一個結果。剩下的三個結果，估計要跑四十幾天。

但是從

https://www.pentoma.de/download-loesungsprogramme/

下載的破解程式，五秒內能把任何2D，3D形狀的所有拼法都算出來。

我懷疑他用了雙指針之類的算法（我也不是很懂）。

總之我相信有比逐步暴力破解更高級的算法，但是我不是數學家和算法專家，所以我不會。

hujunhua

巨复杂的两个7×7的A类图案。零自由度。
短线虽多，整体却是高度连通的，了无离散拼凑的痕迹。所以，短线没什么不好看的，不需要优化掉。
7x7图案的四个中心方是固定唯一的，便于搜索，解数应比6X6的多一些，值得 mathe 搜索一番。

mathe

偶数格子和奇数格子的代码还是有些稍微不同。
E7.zip (29.18 KB, 下载次数: 1)

2024-7-21 13:25 上传

点击文件名下载附件

7*7的结果如上。当然奇数格子由于倾斜边不同穿过中间部分，数目会少很多，而且只有A类的，所以扩大了总边数的搜索范围。

mathe

我们前面一直说中心和整个图形重叠的正方形数目是4个，实际上应该改为4的倍数，因为还可以是0个，只是这样的图形通常是下面这样的
也就是图像分成不连续的四块，不是很好的结果。

当然我们也可以通过无用线段把它们连接起来，还可以减少线段的数目：

当然也有少数不含无用边而且连续的，如下图：

中心0个正方形的，我把它放在E类，7*7的结果如附件，大部分是“不良好”的E类。

ejsoon

mathe 发表于 2024-7-21 15:25
我们前面一直说中心和整个图形重叠的正方形数目是4个，实际上应该改为4的倍数，因为还可以是0个，只是这样 ...

看來七方是一個待開發的領域。

是否可以考慮加上「外圍是一個大正方形、所有線段都要連成一片」的條件之後，搜尋下九方的圖？

hujunhua

每种图案按它的自由度（如果大于零）进行调整可适应多种尺寸的网格，必定存在一个最小网格，其大小存在一个上限。
但是13x13离上限还远。下图的自由度是4，最小网格24X24。
（2×2×2×2+4×2=24）

hujunhua

上图自由部分在外围，先乘后加。本图自由部分在核心，先加后乘，所得网格更大。
(2+4×2)×2×2×2=80

hujunhua

如果上图的内部黑框换成下图，则乘法的起始边长为2×9，最后将得到9×2×2×2×2=144的边长。
整图太大要暴屏了，自行脑补一下。


一般来说，我们只要求图案由一个完整的大正方形及其内部组成，不要求内部全部连通.
按此原义，按下图所示层层转角45°相套，最小网格可以达到甚至超过16380×16380.

ejsoon

hujunhua 发表于 2024-7-22 01:56
上图自由部分在外围，先乘后加。本图自由部分在核心，先加后乘，所得网格更大。
(2+4×2)×2×2×2=80
...

或許需要加上「只用16線」或「最多24線」的條件。那麼就將能證明最大網格是12方。

gxqcn

格点图的大小，是用“格”，还是用“点”定义？
即：关于选用“网格”还是“格点”描述，我最初是有过纠结的。

但综合评定下来，更倾向于用后者，
因为我们构造的图，都是基于格点间的连线，而非网格内的涂色，
若用网格，好处是人眼对其可更快识别计数吧。