python暴力穷举求所有四阶幻方

发表于 分类于 本文字数： 366 阅读时长 ≈ 1 分钟

四阶幻方构造方法

将 1-16 填入4×4的方格里，一共有 16! = 20922789888000 种组合，计算量有点大。

可以先假设其中的 7 个数（用 a-g 表示），就可以推出其他数字：
a b c 34-a-b-c
d e f 34-d-e-f
34-2a-b-c-d+f+g g 34-e-f-g 2a+b+c+d+e-g-34
a+b+c-f-g 34-b-e-g -c+e+g -a+f+g

这样就减少到 A(16,7) = 16! / 9! = 57657600 种组合。

  • python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import itertools
import numpy as np


def gen_ms():
    # itertools.permutations 函数 可以生成排列组合
    for i in itertools.permutations(range(1, 17), 7):
        (a, b, c, d, e, f, g) = i
        
        ms = np.zeros(16, dtype=int)
        ms[0] = a
        ms[1] = b
        ms[2] = c
        ms[3] = 34 - a - b - c

        ms[4] = d
        ms[5] = e
        ms[6] = f
        ms[7] = 34 - d - e - f

        ms[8] = 34 - 2 * a - b - c - d + f + g
        ms[9] = g
        ms[10] = 34 - e - f - g
        ms[11] = 2 * a + b + c + d + e - g -34

        ms[12] = a + b + c - f - g
        ms[13] = 34 - b - e - g
        ms[14] = -c + e + g
        ms[15] = -a + f + g
        
        # 判断
        if np.max(ms) > 16 or np.min(ms) < 1 or len(np.unique(ms)) < 16:
            continue

        print(ms)

这是最直观的的穷举方法，性能有点弱鸡，跑完要 4-5 分钟。。。

总共有 7040 种幻方，包含对称、镜像的形式；
所以不重复的是 7040 / 8 = 880 种。

PS：三阶幻方介绍

三阶幻方又叫九宫格，最早是《河图洛书》的描述：

二四为肩，六八为足，左七右三，戴九履一
4 9 2
3 5 7
8 1 6