六边形上19个黑点上不同数字求所有的解！
19个黑点上，放上1到19共19个不同数字，使得每个小三角形（注意有6个小三角形）的每边上的三个数加起来都是22. Good luck!程序求所有的解！ 除了暴力搜索，还有什么好办法吗？ 风云剑 发表于 2019-5-10 09:00
除了暴力搜索，还有什么好办法吗？
除了暴力搜索，就是人肉分析罗。为了人肉方便，推荐按下面图1对19个黑点进行分组编号标记。
https://bbs.emath.ac.cn/forum.php?mod=attachment&aid=OTA0N3wxOGZjMzM0ZnwxNTU3OTk1MTA1fDI0MTF8MTYxNTk%3D&noupdate=yes
图1 19个点的分组和编号标记
（这贴原先的内容只是一些数据罗列，现在将后面的标记图提前到此，以便简化人肉分析的表述
------hujunhua, 2019-5-16, 16:45）
风云剑 发表于 2019-5-10 09:00
除了暴力搜索，还有什么好办法吗？
期待大佬程序 风云剑 发表于 2019-5-10 09:00
除了暴力搜索，还有什么好办法吗？
https://bbs.emath.ac.cn/forum.php?mod=attachment&aid=OTA0OHw0YjM4M2Y0MHwxNTU3OTk1NTk5fDI0MTF8MTYxNTk%3D&noupdate=yes
图2 一些和为常数的导出组合
人肉分析离不开一些特定的和为常数的导出组合，如图2所示。
组号表示组元之和，设A=2a。
一、边心大三角组合：图2所示俩大三角形顶点之和相等。即
E12+E34+E56=E23+E45+E61=E/2=29+5a
显然，对于给定的E组，分成两个大三角组合的划分是唯一的。
二、菱形组合：图2所示三色菱形顶点之和相等，即
R1+E23+R4+E56=R2+E34+R5+E61=E12+R3+E45+R6=(R+E)/3=51+a
三、小三角形组合：Ri+Rj-Eij=22-2A
四、径向双数组合：Ri+Vi=22-A
由A+(22-2A)=22-A, (11-a)+(11-a)=22-A 知 22-2A 和 11-a 属于E组。
五、V=37-5a, R=95-7a, E=58+5A
（这贴原先的内容只是一些数据罗列，现在将后面的导出组合提前到此，以便简化人肉分析的表述
------hujunhua, 2019-5-16, 16:45）
手工分析不难，因为结构和数据都比较特殊。
结构的特殊表现在中心重数高，数据的特殊在于 22 是最小的幻方数，故我们A>2时一开始就可以如下图填好五个数：
1
19
2
18
O
O
O
3
O
O
O
O
O
O
O
O
O
O
O
由楼上2V=74-5A 化为 A=(74-2V)/5因 V ≥1+2+...+6=21, 所以 A≤(74-42)/5=32/5。由此得出中心数 A 只能是2, 4, 6三者之一。
易证 A=6 时无解。这时始图可以翻开更多的格进化为
1
19
2
18
15
14
O
3
13
6
O
O
O
O
O
O
O
O
O
（图的进化标识：黑色为已知数，红色为新填数，蓝色为根据新填数的推导填数。以下相同）
考察17必带1+4 或者2+3，但上图中 1 已满邻，2、3异边，故知17已经不可安排。
A=4时， 始图进化为
1
19
2
18
17
16
O
3
15
4
O
O
O
O
O
O
O
O
O
A=4时，22-2A=14, 11-a=9, 这两个属于E组，由于14必带2+6或者3+5，故始图进化出以下两个分枝：
分枝1：14+3+5
119 2
18
17
16
O
3
15
4
O
O
14
13
O
6
5
O
O
14二分之后，9在分化图中只有两个可选格，故亦二分。分枝2：14+2+6
1
19
2
18
17
16
14
3
15
4
12
6
O
O
O
O
O
7
O
14二分之后，9在分化图中只有两个可选格，故亦二分。
分枝1.1：9+2+11
1
19
2
18
17
16
9
3
15
4
7
11
14
13
13
6
5
12
5
5, 13重复，舍弃分枝1.2：9+5+8
1
19
2
18
17
16
12
3
15
4
10
8
14
13
10
6
5
9
8
8, 10重复，舍弃分枝2.1：9+6+7
1
19
2
18
17
16
14
3
15
4
12
6
1110 11
9
8
7
7
7, 11重复，舍弃分枝2.2：9+3+10
1
19
2
18
17
16
14
3
15
4
12
6
9
8 1311
10
7
5
唯一解。
最后A=2的情况，始图如下：
1
18
3
O
19
17
O
O
O
2
O
O
O
O
O
O
O
O
O
11-a=10属于E组，10可带1+11, 3+9, 4+8, 5+7，分枝较多，应该还需要计算机枚举。
风云剑 发表于 2019-5-10 09:00
除了暴力搜索，还有什么好办法吗？
在一个合格的填法中，将所有的数都对2取余，不考虑对称的区别，容易得出奇偶分布只有以下两种
1 0 1
11 1 1
0 0 0 0 0
0 0 1 1
0 1 1
A=4, R, V, E/2皆为奇数
1 0 1
1 1 1 0
0 0 0 1 1
0 0 1 0
0 1 1
A=2, R, V, E/2皆为偶数
mathe 发表于 2019-5-10 22:08
手工分析不难，因为结构和数据都比较特殊。
...
接6楼，中心为2的比较特殊，在于 Ri+Vi=20, 正好是互补对。
一共是9个互补对，5奇4偶。
除了2+18还剩8个，所以E组有两个互补对，一奇一偶（由楼上奇偶图知）。
18和10属于E组，易知两者必属于同一个E/2三角组，否则两个E/2组必定各含一奇一偶的互补对，但这样一个和为20+18，一个和为20+10，不相等。
18和10所在E/2组剩下一角为6 → 另一个E/2组为14+奇互补对。
1、如此一来，径向双数组合 Ri+Vi=20还有以下7选6
19+1（始图所含，必选）
17+3（始图所含，必选）
16+4（偶对，必选）
12+8（偶对，必选）
15+5（以下奇对3选2）
13+7
11+9
其中前4必选，后面3个奇对选其2，剩1个奇对归入14所在E/2组。
2、V=32去掉含 10, 6 的还有3解
=1+3+4+5+7+12
=1+3+4+5+8+11
=1+3+4+7+8+9 风云剑 发表于 2019-5-10 09:00
除了暴力搜索，还有什么好办法吗？
用线性规划来做，不过，好像是无解。
data={{1,2,3},{1,4,8},{1,5,10},{3,6,10},{3,7,12},{8,9,10},{10,11,12},{8,13,17},{10,14,17},{10,15,19},{12,16,19},{17,18,19}};
m=SparseArray]],{d,Length}],1],{12,19}];
LinearProgramming,Join,i],{i,0,17}]],Join,ConstantArray],ConstantArray[{1,19},19]] wayne 发表于 2019-5-11 19:09
用线性规划来做，不过，好像是无解。
就这么4个基本解(如果不计旋转,翻转，填法是唯一的)。
1192
181716
14
3154126
981311
1075
1183
9191714
1282155
6161310
4117
1183
13191714
8122155
101696
4711
1183
14191715
7132164
6111210
958