六边形上19个黑点上不同数字求所有的解！

markfang2050

19个黑点上，放上1到19共19个不同数字，使得每个小三角形（注意有6个小三角形）的每边上的三个数加起来都是22. Good luck!
程序求所有的解！

风云剑

除了暴力搜索，还有什么好办法吗？

王守恩

风云剑 发表于 2019-5-10 09:00
除了暴力搜索，还有什么好办法吗？

除了暴力搜索，就是人肉分析罗。为了人肉方便，推荐按下面图1对19个黑点进行分组编号标记。

图1   19个点的分组和编号标记
（这贴原先的内容只是一些数据罗列，现在将后面的标记图提前到此，以便简化人肉分析的表述
------hujunhua, 2019-5-16, 16:45）

markfang2050

风云剑 发表于 2019-5-10 09:00
除了暴力搜索，还有什么好办法吗？

期待大佬程序

王守恩

风云剑 发表于 2019-5-10 09:00
除了暴力搜索，还有什么好办法吗？

图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）

mathe

手工分析不难，因为结构和数据都比较特殊。
结构的特殊表现在中心重数高，数据的特殊在于 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 1 19 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 11 10 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 13 11 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 1 1 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

wayne

风云剑 发表于 2019-5-10 09:00
除了暴力搜索，还有什么好办法吗？

用线性规划来做，不过，好像是无解。

1. 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}};
   
2. m=SparseArray[Flatten[Table[Map[{d,#}->1&,data[[d]]],{d,Length[data]}],1],{12,19}];
   
3. LinearProgramming[PadRight[{1},19],Join[m,Table[RotateRight[PadRight[{-1,1},19],i],{i,0,17}]],Join[ConstantArray[22,12],ConstantArray[1,18]],ConstantArray[{1,19},19]]

复制代码

王守恩

wayne 发表于 2019-5-11 19:09
用线性规划来做，不过，好像是无解。

就这么4个基本解(如果不计旋转,翻转，填法是唯一的)。

1 19 2 18 17 16 14 3 15 4 12 6 9 8 13 11 10 7 5	1 18 3 9 19 17 14 12 8 2 15 5 6 16 13 10 4 11 7
1 18 3 13 19 17 14 8 12 2 15 5 10 16 9 6 4 7 11	1 18 3 14 19 17 15 7 13 2 16 4 6 11 12 10 9 5 8