棋子排列问题

markfang2050

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

hujunhua

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

	●	●	●
●	○
●		○
●			○

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

● ● ● ● ○ ● ○ ○ ○ A21

● ● ● ● ○ ● ○ ○ ○ A22

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

hujunhua

黑子为 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

816个

markfang2050

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

第二行:1,1,0,0

第三行:1,0,0,1

第四行:0,0,1,1

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

hujunhua

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

结果确实是816

1. Coefficient[(a b + b c + c d + a c + b d + a d + a b c + a b d +
   
2.      b c d + a c d )^4, a^3 b^2 c^2 d^2] +
   
3. Coefficient[(a b + b c + c d + a c + b d + a d + a b c + a b d +
   
4.      b c d + a c d )^4, a^2 b^3 c^2 d^2] +
   
5. Coefficient[(a b + b c + c d + a c + b d + a d + a b c + a b d +
   
6.      b c d + a c d )^4, a^2 b^2 c^3 d^2] +
   
7. Coefficient[(a b + b c + c d + a c + b d + a d + a b c + a b d +
   
8.      b c d + a c d )^4, a^2 b^2 c^2 d^3]

复制代码

耗时几乎为零。

mathe

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

markfang2050  耗时是打印结果造成的

用MMA会快很多

1. p = Select[
   
2.    SparseArray[#,
   
3.       4] & /@ (Table[{i1, i2, i3, i4} // Flatten, {i1,
   
4.         Map[{1, #} -> 1 &, Subsets[Range[4], {2, 3}], {2}]}, {i2,
   
5.         Map[{2, #} -> 1 &, Subsets[Range[4], {2, 3}], {2}]}, {i3,
   
6.         Map[{3, #} -> 1 &, Subsets[Range[4], {2, 3}], {2}]}, {i4,
   
7.         Map[{4, #} -> 1 &, Subsets[Range[4], {2, 3}], {2}]}] //
   
8.       Flatten[#, 3] &),
   
9.    SameQ[Total[#] // Sort, {2, 2, 2, 3}] &&
   
10.      SameQ[Total[#, {2}] // Sort, {2, 2, 2, 3}] &];
    
11. % // Length
    
12. MatrixForm /@ p

复制代码

全部结果打印出来也不到1秒。
也可以在8秒内画出所有棋盘结果

1. MatrixPlot[#, ColorFunction -> "Monochrome", ImageSize -> Tiny,
   
2.    Mesh -> All, Frame -> None, FrameTicks -> None] & /@ p // AbsoluteTiming

复制代码