一道二年级数学：填数字

aoe1981

　　如果是4条边，每边4空位，每边和从17起直到22时才会有解，此后每边和值越大，可能结果数越多。每边和为22时结果总数：1920个，去重后结果：240个。粘贴如下：

1-5-12-4-6-9-3-7-10-2-8-11
1-5-12-4-6-9-3-7-10-2-11-8
1-5-12-4-6-9-3-10-7-2-8-11
1-5-12-4-6-9-3-10-7-2-11-8
1-5-12-4-6-10-2-8-9-3-7-11
1-5-12-4-6-10-2-8-9-3-11-7
1-5-12-4-6-10-2-9-8-3-7-11
1-5-12-4-6-10-2-9-8-3-11-7
1-5-12-4-7-8-3-6-11-2-9-10
1-5-12-4-7-8-3-6-11-2-10-9
1-5-12-4-7-8-3-11-6-2-9-10
1-5-12-4-7-8-3-11-6-2-10-9
1-5-12-4-7-9-2-6-11-3-8-10
1-5-12-4-7-9-2-6-11-3-10-8
1-5-12-4-7-9-2-11-6-3-8-10
1-5-12-4-7-9-2-11-6-3-10-8
1-5-12-4-8-7-3-6-11-2-9-10
1-5-12-4-8-7-3-6-11-2-10-9
1-5-12-4-8-7-3-11-6-2-9-10
1-5-12-4-8-7-3-11-6-2-10-9
1-5-12-4-9-6-3-7-10-2-8-11
1-5-12-4-9-6-3-7-10-2-11-8
1-5-12-4-9-6-3-10-7-2-8-11
1-5-12-4-9-6-3-10-7-2-11-8
1-5-12-4-9-7-2-6-11-3-8-10
1-5-12-4-9-7-2-6-11-3-10-8
1-5-12-4-9-7-2-11-6-3-8-10
1-5-12-4-9-7-2-11-6-3-10-8
1-5-12-4-10-6-2-8-9-3-7-11
1-5-12-4-10-6-2-8-9-3-11-7
1-5-12-4-10-6-2-9-8-3-7-11
1-5-12-4-10-6-2-9-8-3-11-7
1-6-11-4-5-10-3-8-9-2-7-12
1-6-11-4-5-10-3-8-9-2-12-7
1-6-11-4-5-10-3-9-8-2-7-12
1-6-11-4-5-10-3-9-8-2-12-7
1-6-11-4-7-8-3-5-12-2-9-10
1-6-11-4-7-8-3-5-12-2-10-9
1-6-11-4-7-8-3-12-5-2-9-10
1-6-11-4-7-8-3-12-5-2-10-9
1-6-11-4-7-9-2-5-12-3-8-10
1-6-11-4-7-9-2-5-12-3-10-8
1-6-11-4-7-9-2-12-5-3-8-10
1-6-11-4-7-9-2-12-5-3-10-8
1-6-11-4-8-7-3-5-12-2-9-10
1-6-11-4-8-7-3-5-12-2-10-9
1-6-11-4-8-7-3-12-5-2-9-10
1-6-11-4-8-7-3-12-5-2-10-9
1-6-11-4-9-7-2-5-12-3-8-10
1-6-11-4-9-7-2-5-12-3-10-8
1-6-11-4-9-7-2-12-5-3-8-10
1-6-11-4-9-7-2-12-5-3-10-8
1-6-11-4-10-5-3-8-9-2-7-12
1-6-11-4-10-5-3-8-9-2-12-7
1-6-11-4-10-5-3-9-8-2-7-12
1-6-11-4-10-5-3-9-8-2-12-7
1-6-12-3-5-10-4-7-9-2-8-11
1-6-12-3-5-10-4-7-9-2-11-8
1-6-12-3-5-10-4-9-7-2-8-11
1-6-12-3-5-10-4-9-7-2-11-8
1-6-12-3-7-8-4-5-11-2-9-10
1-6-12-3-7-8-4-5-11-2-10-9
1-6-12-3-7-8-4-11-5-2-9-10
1-6-12-3-7-8-4-11-5-2-10-9
1-6-12-3-7-10-2-5-11-4-8-9
1-6-12-3-7-10-2-5-11-4-9-8
1-6-12-3-7-10-2-11-5-4-8-9
1-6-12-3-7-10-2-11-5-4-9-8
1-6-12-3-8-7-4-5-11-2-9-10
1-6-12-3-8-7-4-5-11-2-10-9
1-6-12-3-8-7-4-11-5-2-9-10
1-6-12-3-8-7-4-11-5-2-10-9
1-6-12-3-8-9-2-5-11-4-7-10
1-6-12-3-8-9-2-5-11-4-10-7
1-6-12-3-8-9-2-11-5-4-7-10
1-6-12-3-8-9-2-11-5-4-10-7
1-6-12-3-9-8-2-5-11-4-7-10
1-6-12-3-9-8-2-5-11-4-10-7
1-6-12-3-9-8-2-11-5-4-7-10
1-6-12-3-9-8-2-11-5-4-10-7
1-6-12-3-10-5-4-7-9-2-8-11
1-6-12-3-10-5-4-7-9-2-11-8
1-6-12-3-10-5-4-9-7-2-8-11
1-6-12-3-10-5-4-9-7-2-11-8
1-6-12-3-10-7-2-5-11-4-8-9
1-6-12-3-10-7-2-5-11-4-9-8
1-6-12-3-10-7-2-11-5-4-8-9
1-6-12-3-10-7-2-11-5-4-9-8
1-7-10-4-5-11-2-8-9-3-6-12
1-7-10-4-5-11-2-9-8-3-6-12
1-7-10-4-6-9-3-5-12-2-8-11
1-7-10-4-6-9-3-5-12-2-11-8
1-7-10-4-6-9-3-12-5-2-8-11
1-7-10-4-6-9-3-12-5-2-11-8
1-7-10-4-9-6-3-5-12-2-8-11
1-7-10-4-9-6-3-5-12-2-11-8
1-7-10-4-9-6-3-12-5-2-8-11
1-7-10-4-9-6-3-12-5-2-11-8
1-7-10-4-11-5-2-8-9-3-6-12
1-7-10-4-11-5-2-9-8-3-6-12
1-7-11-3-5-12-2-6-10-4-8-9
1-7-11-3-5-12-2-6-10-4-9-8
1-7-11-3-5-12-2-10-6-4-8-9
1-7-11-3-5-12-2-10-6-4-9-8
1-7-11-3-8-9-2-6-10-4-5-12
1-7-11-3-8-9-2-10-6-4-5-12
1-7-11-3-9-8-2-6-10-4-5-12
1-7-11-3-9-8-2-10-6-4-5-12
1-7-11-3-12-5-2-6-10-4-8-9
1-7-11-3-12-5-2-6-10-4-9-8
1-7-11-3-12-5-2-10-6-4-8-9
1-7-11-3-12-5-2-10-6-4-9-8
1-7-12-2-5-11-4-6-9-3-8-10
1-7-12-2-5-11-4-6-9-3-10-8
1-7-12-2-5-11-4-9-6-3-8-10
1-7-12-2-5-11-4-9-6-3-10-8
1-7-12-2-6-11-3-5-10-4-8-9
1-7-12-2-6-11-3-5-10-4-9-8
1-7-12-2-6-11-3-10-5-4-8-9
1-7-12-2-6-11-3-10-5-4-9-8
1-7-12-2-8-9-3-5-10-4-6-11
1-7-12-2-8-9-3-10-5-4-6-11
1-7-12-2-9-8-3-5-10-4-6-11
1-7-12-2-9-8-3-10-5-4-6-11
1-7-12-2-11-5-4-6-9-3-8-10
1-7-12-2-11-5-4-6-9-3-10-8
1-7-12-2-11-5-4-9-6-3-8-10
1-7-12-2-11-5-4-9-6-3-10-8
1-7-12-2-11-6-3-5-10-4-8-9
1-7-12-2-11-6-3-5-10-4-9-8
1-7-12-2-11-6-3-10-5-4-8-9
1-7-12-2-11-6-3-10-5-4-9-8
1-8-9-4-5-10-3-6-11-2-7-12
1-8-9-4-5-10-3-11-6-2-7-12
1-8-9-4-5-11-2-7-10-3-6-12
1-8-9-4-5-11-2-10-7-3-6-12
1-8-9-4-6-10-2-5-12-3-7-11
1-8-9-4-6-10-2-12-5-3-7-11
1-8-9-4-10-5-3-6-11-2-7-12
1-8-9-4-10-5-3-11-6-2-7-12
1-8-9-4-10-6-2-5-12-3-7-11
1-8-9-4-10-6-2-12-5-3-7-11
1-8-9-4-11-5-2-7-10-3-6-12
1-8-9-4-11-5-2-10-7-3-6-12
1-8-10-3-5-12-2-7-9-4-6-11
1-8-10-3-5-12-2-9-7-4-6-11
1-8-10-3-6-9-4-5-11-2-7-12
1-8-10-3-6-9-4-11-5-2-7-12
1-8-10-3-6-11-2-7-9-4-5-12
1-8-10-3-6-11-2-9-7-4-5-12
1-8-10-3-9-6-4-5-11-2-7-12
1-8-10-3-9-6-4-11-5-2-7-12
1-8-10-3-11-6-2-7-9-4-5-12
1-8-10-3-11-6-2-9-7-4-5-12
1-8-10-3-12-5-2-7-9-4-6-11
1-8-10-3-12-5-2-9-7-4-6-11
1-8-11-2-5-12-3-6-9-4-7-10
1-8-11-2-5-12-3-9-6-4-7-10
1-8-11-2-7-9-4-5-10-3-6-12
1-8-11-2-7-9-4-10-5-3-6-12
1-8-11-2-7-10-3-6-9-4-5-12
1-8-11-2-7-10-3-9-6-4-5-12
1-8-11-2-9-7-4-5-10-3-6-12
1-8-11-2-9-7-4-10-5-3-6-12
1-8-11-2-10-7-3-6-9-4-5-12
1-8-11-2-10-7-3-9-6-4-5-12
1-8-11-2-12-5-3-6-9-4-7-10
1-8-11-2-12-5-3-9-6-4-7-10
1-9-8-4-5-10-3-6-11-2-7-12
1-9-8-4-5-10-3-11-6-2-7-12
1-9-8-4-5-11-2-7-10-3-6-12
1-9-8-4-5-11-2-10-7-3-6-12
1-9-8-4-6-10-2-5-12-3-7-11
1-9-8-4-6-10-2-12-5-3-7-11
1-9-8-4-10-5-3-6-11-2-7-12
1-9-8-4-10-5-3-11-6-2-7-12
1-9-8-4-10-6-2-5-12-3-7-11
1-9-8-4-10-6-2-12-5-3-7-11
1-9-8-4-11-5-2-7-10-3-6-12
1-9-8-4-11-5-2-10-7-3-6-12
1-9-10-2-5-11-4-7-8-3-6-12
1-9-10-2-5-11-4-8-7-3-6-12
1-9-10-2-5-12-3-7-8-4-6-11
1-9-10-2-5-12-3-8-7-4-6-11
1-9-10-2-6-11-3-7-8-4-5-12
1-9-10-2-6-11-3-8-7-4-5-12
1-9-10-2-11-5-4-7-8-3-6-12
1-9-10-2-11-5-4-8-7-3-6-12
1-9-10-2-11-6-3-7-8-4-5-12
1-9-10-2-11-6-3-8-7-4-5-12
1-9-10-2-12-5-3-7-8-4-6-11
1-9-10-2-12-5-3-8-7-4-6-11

　　但是当我找5条边，每边5个空位时，可以出结果的和值时，程序和电脑已国不从心，递归控制次数放大为10亿次，时间太漫长，试到33时就没有反应了……

aoe1981

1-10-7-4-5-11-2-8-9-3-6-12
1-10-7-4-5-11-2-9-8-3-6-12
1-10-7-4-6-9-3-5-12-2-8-11
1-10-7-4-6-9-3-12-5-2-8-11
1-10-7-4-9-6-3-5-12-2-8-11
1-10-7-4-9-6-3-12-5-2-8-11
1-10-7-4-11-5-2-8-9-3-6-12
1-10-7-4-11-5-2-9-8-3-6-12
1-10-8-3-5-12-2-7-9-4-6-11
1-10-8-3-5-12-2-9-7-4-6-11
1-10-8-3-6-9-4-5-11-2-7-12
1-10-8-3-6-9-4-11-5-2-7-12
1-10-8-3-6-11-2-7-9-4-5-12
1-10-8-3-6-11-2-9-7-4-5-12
1-10-8-3-9-6-4-5-11-2-7-12
1-10-8-3-9-6-4-11-5-2-7-12
1-10-8-3-11-6-2-7-9-4-5-12
1-10-8-3-11-6-2-9-7-4-5-12
1-10-8-3-12-5-2-7-9-4-6-11
1-10-8-3-12-5-2-9-7-4-6-11
1-10-9-2-5-11-4-7-8-3-6-12
1-10-9-2-5-11-4-8-7-3-6-12
1-10-9-2-5-12-3-7-8-4-6-11
1-10-9-2-5-12-3-8-7-4-6-11
1-10-9-2-6-11-3-7-8-4-5-12
1-10-9-2-6-11-3-8-7-4-5-12
1-10-9-2-11-5-4-7-8-3-6-12
1-10-9-2-11-5-4-8-7-3-6-12
1-10-9-2-11-6-3-7-8-4-5-12
1-10-9-2-11-6-3-8-7-4-5-12
1-10-9-2-12-5-3-7-8-4-6-11
1-10-9-2-12-5-3-8-7-4-6-11
1-11-6-4-5-10-3-8-9-2-7-12
1-11-6-4-5-10-3-9-8-2-7-12
1-11-6-4-10-5-3-8-9-2-7-12
1-11-6-4-10-5-3-9-8-2-7-12
1-11-7-3-8-9-2-6-10-4-5-12
1-11-7-3-8-9-2-10-6-4-5-12
1-11-7-3-9-8-2-6-10-4-5-12
1-11-7-3-9-8-2-10-6-4-5-12
1-11-8-2-7-9-4-5-10-3-6-12
1-11-8-2-7-9-4-10-5-3-6-12
1-11-8-2-7-10-3-6-9-4-5-12
1-11-8-2-7-10-3-9-6-4-5-12
1-11-8-2-9-7-4-5-10-3-6-12
1-11-8-2-9-7-4-10-5-3-6-12
1-11-8-2-10-7-3-6-9-4-5-12
1-11-8-2-10-7-3-9-6-4-5-12

香川群子

aoe1981 发表于 2018-6-7 19:18
没说到重点上，上面两组您也认为是不同的，您的结果中也有，关键是下组结果您的没有：

1-7-9-6-2-12-3-1 ...

问题原因很简单。

因为我对顶点取值范围做了限制=h/2，
按你最初的题目的条件是足够了，
但是当h增大时，组合可能性变多，所以这个限制造成了有些正确组合没有被计算在内。

可以修改代码，取值范围=h-3即可。

香川群子

liu-aguang 发表于 2018-6-7 19:26
算法容易想到, 就是去重麻烦.
1. 求可能的4个顶点组合(顶点数值不会超过600): 即1-6范围取4个数的组合;
...

我的递归算法，思路和你的想法应该是较为接近的。

1. 顶点递归排列组合，过程中数组检查去重复。
2. 计算填入中间数（满足总和以及不重复）
3. 得到的有效组合用低位排序和反转低位排序的方法得到标准结果，字典去重复。

第3步，无需考虑起点位置和顺序。

jiangtaowoo

这个题目和八皇后问题类似，可以采用相同算法，替换里面的冲突计算函数即可，思路为：
1、初始化解为空棋盘（这个问题相当于一个有8个位置的棋盘）
2、对每个解，往棋盘放置下一个棋子，扩展为若干个解，规则是
      2.1 下一个位置有n种取值（本题里可取值为1~9的数字）
      2.2 判断每种取值与当前棋盘摆放形势是否冲突，如果不冲突，用原有棋盘+新摆放棋子构成一个新的解
3、当摆完所有棋盘位置时，所有的解都被枚举出来了（并且在扩展棋盘过程种，已经过滤掉了不可能路径）

对于解的去重，如果把棋盘的每个位置看做是固定的序号的话，则不存在重复解。
如果把棋盘的位置看成可以顺时针，逆时针旋转的话，那么
[0,1,2,3,4,5,6,7]    --- 这个视为默认位置次序，与下列七种数据摆放次序是重复的，通过这个关系可以实现“去重”
[0,7,6,5,4,3,2,1]   --- 逆时针
[6,5,4,3,2,1,0,7]  ---  逆时针，移动2格
[4,3,2,1,0,7,6,5]  ---  逆时针，移动4格
[2,1,0,7,6,5,4,3]  ---  逆时针，移动6格
[2,3,4,5,6,7,0,1] ---   顺时针移动2格
[4,5,6,7,0,1,2,3] ---   顺时针移动4格
[6,7,0,1,2,3,4,5] ---   顺时针移动6格

顺便批判一下枚举所有排列的算法，这种算法在棋盘size增大时越来越难以计算，所以还是应该在计算过程中去不断过滤掉无效解。

aoe1981

香川群子 发表于 2018-6-8 09:21
问题原因很简单。

因为我对顶点取值范围做了限制=h/2，

试了下，确实如此……

比我写的简洁多了……

香川群子

aoe1981 发表于 2018-6-9 11:47
试了下，确实如此……

比我写的简洁多了……

我修改了取数范围的bug
对于m=4个顶点即4条边，每条边中间个数n=1个数（即每边3个数），总和H=14时，

如果顶点的循环排列组合取数范围=1 To H (或H-3)，则计算结果总数=184组解，去重复后剩余23组解。

但是这样的计算递归无效循环太多了。
为了避免大量重复计算，在开始循环前写了个小循环检查当前最小数字n。
这样剪枝一下，递归计算次数缩减5-6倍，效率高多了。计算组合数减少到145组，去重复后剩余结果数还是23组解。

香川群子

增加了每条边中间个数>=1的复杂情况，但是实际上中间结果只取组合即可（排列顺序对顶点结果无影响）

这样计算4条边每边中间2个数的情况，去掉重复的结果只有15组（乘以中间排列2^4=16之后就还原为240种结果和你的计算结果一致）

香川群子

复杂多边形总和相同的递归计算还有一些bug，修正了一下。

aoe1981

香川群子 发表于 2018-6-11 10:29
复杂多边形总和相同的递归计算还有一些bug，修正了一下。

香川大侠一出马，问题解决便到达极致了……