markfang2050 发表于 2019-6-26 08:24:21

棋子排列问题

5年级数学。要求给出所有排列的图示。程序语言不限制。

hujunhua 发表于 2019-6-26 13:20:13

9=2+2+2+3是唯一的四质数分解方案
我们记全部合适的放法之集为 A.
A 可分为两个子集:A1={3子行与3子列交于空者},A2={3子行与3子列交于子者}。
一个合适的放法经过行变换和列变换后还是一个合适的放法。行变换和列变换各有4!=24个,所以行、列变换群的阶为242=576。
先找出 A 在行、列变换下的商集(商集即变换下的各等价类之集,一个等价类可以用该类中的任一元素代表)。
A1 显然只有1个等价类,以下是它的一个代表。A1中的任一元素(放法)都可变换成该代表.

●●●
●○
● ○
● ○
A2 有2个等价类,我们记为 A21、A22,以下是它们的代表.


●●●
●○
● ○
○○
A21
●●●
● ○
● ○
○○
A22
剩下的事情就是计算每个等价类的阶,即上述各代表在 576 个行列变换下能生成多少个不重合的放法。

hujunhua 发表于 2019-6-26 13:57:46

黑子为 A1 v.s. A2 的分类特征,显然每个分类特征都有16个不同的衍生特征(包括代表自身)。
A1的每个衍生特征再放3个白子,显然是 3! 种放法。故|A1|=16×3!=96
A21的每个衍生特征再放4个白子,共有4个不重合放法。故|A21|=16×4=64
A22的每个衍生特征再放4个白子,唯有1个不重合放法。故|A22|=16, |A2|=|A21|+|A22|=80。
|A|=|A1|+|A2|=176。

176个图都摆出来,有点多。把3个代表再放白子的所有图摆出来,共11个图,还可以接受。

markfang2050 发表于 2019-6-26 14:05:30

816个:lol

markfang2050 发表于 2019-6-26 14:08:04

存在第816组解。
第一行:1,1,1,0

第二行:1,1,0,0

第三行:1,0,0,1

第四行:0,0,1,1

4*4正方形方格放9枚棋子,每行每列的棋子个数均为质数,总共存在816组方法。
程序运行时间 55.195427656173706 秒。

hujunhua 发表于 2019-6-26 14:55:44

hujunhua 发表于 2019-6-26 13:57
黑子为 A1 v.s. A2 的分类特征,显然每个分类特征都有16个不同的衍生特征(包括代表自身)。
...
@markfang2050
哦,这里有错误。
这个断言只对 A1 成立。
A2 的分类特征应该有9×16个不同的衍生特征(包括代表自身)。
A2 的特征具有以下标记格:1、黑子行和黑子列之公共黑子,记为A。2、空行和空列之公共空格,记为B。
B有16格可选,对于确定的B,A有9格可选。故有9×16个不同的衍生特征。

|A|=96+80×9=816,这就更不可能一个个画出来了。

kastin 发表于 2019-6-26 18:03:32

结果确实是816
Coefficient[(a b + b c + c d + a c + b d + a d + a b c + a b d +
   b c d + a c d )^4, a^3 b^2 c^2 d^2] +
Coefficient[(a b + b c + c d + a c + b d + a d + a b c + a b d +
   b c d + a c d )^4, a^2 b^3 c^2 d^2] +
Coefficient[(a b + b c + c d + a c + b d + a d + a b c + a b d +
   b c d + a c d )^4, a^2 b^2 c^3 d^2] +
Coefficient[(a b + b c + c d + a c + b d + a d + a b c + a b d +
   b c d + a c d )^4, a^2 b^2 c^2 d^3]耗时几乎为零。

mathe 发表于 2019-6-26 18:49:17

hujunhua的方案可以通过数不动点的数目达到。
我们把行、列变换群记为G,前面已指出|G|=4!×4!. 全体放法之集如2楼仍记为A。
所谓不动点,即对某个 a∈A, 满足g∈G, g(a)=a的变换g.
比如 2# 中 A1 的那个代表元,

●●●
●○
● ○
● ○
使之看起来保持不变的变换,显然行1和列1不能动,行2,3,4和列2,3,4必须保持同步交换(转置对称),故有3!=6个不动点.
易证,对任意 a'∈A1, 满足h(a')=a'的不动点 h∈G 也是3!=6个。
因为唯一存在 g'∈G, 使得 a'=g'(a). 故 h(a')=a'←→hg'(a)=g'(a) ←→g'h(a)=g'(a)←→h(a)=a
                                                                                       (G 是交换群)
即 A1中任意元的不动点都与代表元的相同,所以|A1|=|G|/3!=96种。

A21的那个代表元的不动点显然只有一个,即 g 的单位元。
A22的那个代表元的不动点,显然行1,4、列1,4不能动,只能行2,3、列2,3互换,故有4个。
所以|A|=|G|(1/6+1+1/4)=816.

kastin 发表于 2019-6-27 11:46:43

markfang2050耗时是打印结果造成的用MMA会快很多
p = Select[
   SparseArray[#,
      4] & /@ (Table[{i1, i2, i3, i4} // Flatten, {i1,
      Map[{1, #} -> 1 &, Subsets, {2, 3}], {2}]}, {i2,
      Map[{2, #} -> 1 &, Subsets, {2, 3}], {2}]}, {i3,
      Map[{3, #} -> 1 &, Subsets, {2, 3}], {2}]}, {i4,
      Map[{4, #} -> 1 &, Subsets, {2, 3}], {2}]}] //
      Flatten[#, 3] &),
   SameQ // Sort, {2, 2, 2, 3}] &&
   SameQ // Sort, {2, 2, 2, 3}] &];
% // Length
MatrixForm /@ p全部结果打印出来也不到1秒。
也可以在8秒内画出所有棋盘结果
MatrixPlot[#, ColorFunction -> "Monochrome", ImageSize -> Tiny,
   Mesh -> All, Frame -> None, FrameTicks -> None] & /@ p // AbsoluteTiming
页: [1]
查看完整版本: 棋子排列问题