FreedomLy's blog.

【每周一坑】神奇的九宫格

字数统计: 1.2k阅读时长: 5 min
2017/05/15 Share

本周题目:

给定一个3*3的九宫格和1-9九个数字,将9个数字按照一定规则填充进九宫格内,使九宫格内横、竖、斜每条线的和都相等,输出至少一种结果。

示例:

1
2
3
4
5
6
7
def Jiugongge():
'''
>>> Jiugongge()
4 9 2
3 5 7
8 1 6
'''

附加题:

给定一个正整数 N(N >= 1),将 1 - N^2 填充到 N * N 的格子中,使横、竖、斜(对角线)每条线的和都相等,输出至少一种组合。

比如 N 等于 3 时就是 9 宫格, N 等于 4 时为 16 宫格。

思路

在解决问题之前,要先了解一个东西 —— “幻方”。
Wiki上给出的中文定义:

幻方(Magic Square),有时又称魔方(该称呼现一般指立方体的魔术方块)或纵横图,由一组排放在正方形中的整数组成,其每行、每列以及两条对角线上的数之和均相等。通常幻方由从$1$到 $N^{2}$的连续整数组成,其中$N$为正方形的行或列的数目。因此$N$阶幻方有$N$行$N$列,并且所填充的数为从$1$到$N^{2}$。

幻方可以使用$N$阶方阵来表示,方阵的每行、每列以及两条对角线的和都等于常数 $M_{2}(N)$,如果填充数为$1,2,\dots ,N^{2}$,那么有
$$M_{2}(N)={\frac {N(N^{2}+1)}{2}}$$

$N$阶幻方的解题思路分为三种情况:

  1. $N$为奇数
  2. $N$为4的倍数
  3. $N$为其他偶数

1. $N$为奇数

  • 将$1$放在第一行中间一列;
  • 从$2$开始直到$n*n$为止各数依次按下列规则存放,按$45°$方向行走,如向右上,每一个数存放的行比前一个数的行数减$1$,列数加$1$;
  • 如果行列范围超出矩阵范围,则回绕。例如$1$在第一行,则$2$应放在最下一行,列数同样加$1$;
  • 如果按照上述规则确定的位置已有数,或上一个数是第$1$行$n$列时,则把下一个数放在上一个数的下面。

2. $N$为$4$的倍数

采用对称元素交换法。首先把数$1$到$n*n$按从上至下、从左至又的顺序填入矩阵。
然后将方阵的所有$N*N$子方阵中的两对角线上位置的数关于方阵中心作对称交换,即$a(i,j)$与$a(n-1-i, n-1-j)$交换,所有其它位置上的数不变。

3. $N$为非$4$的倍数的偶数(即$4n+2$)

首先把大方阵分解为$4$个奇数字方阵。
按上述奇数幻方给分解的4个子方阵对应赋值,其中:
上左子阵最小$(i)$,下右子阵次小$(i+v)$,下左子阵最大$(i+3v)$,上右子阵次大$(i+2v)$
即$4$个子方阵对应元素相差$v$,其中$v={\frac {n*n}{4}}$
四个子矩阵由小到大排列方式为

$$
\begin{bmatrix}
1 & 3 \
4 & 2 \
\end{bmatrix}
$$

然后作相应的元素交换:$a(i,j)$ 与 $a(i+k,j)$在同一列做对应交换,$(j\lt t或j\gt n-t)$, $a(t,0)与a(t+k,0)$; $a(t,t)$ 与 $a(t+k,t)$ 两对元素交换,其中
$k = n//2,t=(n-2)//4$。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# n为奇数
def oddN():
# 构造二维列表
lst = [[0 for i in range(n)] for i in range(n)]
# 初始化列表位置
x, y = 0, n//2
for num in range(1, n*n+1):
lst[x][y] = num
xa, ya = x-1, y+1
# 回绕情况
if xa < 0:
xa = n-1
if ya > n-1:
ya = 0
# 占位情况
if lst[xa][ya] != 0:
x = x+1
if x > n-1:
x = 0
else:
x, y = xa, ya
return lst

# n为4的倍数
def fourN(n):
# 初始化列表
lst = [[i+j for i in list(range(1,n*n+1))[::n]] for j in range(n)]
# 交换对角线位置
for i in range(n//2):
lst[i][i],lst[n-1-i][n-1-i] = lst[n-1-i][n-1-i],lst[i][i]
lst[i][n-1-i],lst[n-1-i][i] = lst[n-1-i][i],lst[i][n-1-i]
return lst

# n为非4倍数的偶数
# 累加子矩阵
def acc(p, lst):
# print(lst)
for row in lst:
for index in range(len(row)):
row[index] += p

return lst


def fourNplus2(n):
m = n // 2
A, B, C, D = oddN(m), oddN(m), oddN(m), oddN(m)
B = acc(m ** 2, B)
C = acc(m ** 2 * 2, C)
D = acc(m ** 2 * 3, D)
for row_index in range(len(A)):
A[row_index].extend(C[row_index])
D[row_index].extend(B[row_index])
# 合并子矩阵
matrix = A + D
t = (n - 2) // 4
# 列交换
for col_index in range(len(matrix[0])):
if col_index < t or col_index > n - t:
for row_index in range(len(matrix) // 2):
matrix[row_index][col_index], matrix[row_index + m][col_index] = \
matrix[row_index + m][col_index], matrix[row_index][col_index]
# 交换特殊位置
matrix[t][0], matrix[m + t][0] = matrix[m + t][0], matrix[t][0]
matrix[t][t], matrix[m + t][t] = matrix[m + t][t], matrix[t][t]
return matrix

End~


CATALOG
  1. 1. 思路
    1. 1.1. 1. $N$为奇数
    2. 1.2. 2. $N$为$4$的倍数
    3. 1.3. 3. $N$为非$4$的倍数的偶数(即$4n+2$)
  2. 2. Python实现