九宫格问题、16宫格
九宫格（Lo Shu Square）问题
将1到9的数字按照一定方式填入九宫格内。使得每一列、每一行以及两条对角线上的值都相等。
在重庆等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供成都网站设计、网站建设 网站设计制作按需网站策划,公司网站建设,企业网站建设,成都品牌网站建设,营销型网站建设,外贸营销网站建设,重庆网站建设费用合理。
全排列（递归）
首先，用枚举法，生成各种(3, 3)的二维数组：
def perm(li):
"""递归实现列表的全排列
如果输入是[1]，那么返回[[li],]表示有一种排列
如果输入是[1, 2]，期望的返回的是[[1, 2], [2, 1]]，这是要之后的递归实现的
"""
if len(li) <= 1:
return [li]
ret = []
for i in range(len(li)):
s1 = li[i:i + 1] # 取出一个元素，组成一个列表
rest = li[:i] + li[i + 1:] # 剩余的元素组成一个列表
p = perm(rest)
for j in p: # 迭代每一种排列
ret.append(s1 + j) # 和之前取出的1个元素进行拼接
return ret简单验证一下：
>>> perm([1, 2, 3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]递归算法比较费时，如果是9个数字的全排列，要1秒左右。如果数组更大比如(4, 4)就几乎跑不完了：
995 ms ± 12.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)检查函数
各种求和，然后进行检查：
def is_lo_shu_square(arr):
"""接收numpy的二维数组"""
if np.shape(arr)[0] != np.shape(arr)[1]:
return False
d = np.shape(arr)[0]
n = np.sum(arr) / d
for i in np.sum(arr, axis=0):
if i != n:
return False
for i in np.sum(arr, axis=1):
if i != n:
return False
if np.sum(np.eye(d, dtype=int) * arr) != n: # 检查对角线
return False
if np.sum(np.eye(d, dtype=int)[::-1] * arr) != n: # 检查次对角线
return False
return True简单验证一下：
>>> np.array(([1, 1], [1, 1]))
array([[1, 1],
[1, 1]])
>>> a = np.array(([1, 1], [1, 1]))
>>> is_lo_shu_squar(a)
True计算结果
>>> li = [i+1 for i in range(9)]
>>> for i in perm(li):
a = np.array(i).reshape(3, 3)
if is_lo_shu_square(a):
print(a)
[[2 7 6]
[9 5 1]
[4 3 8]]
[[2 9 4]
[7 5 3]
[6 1 8]]
[[4 3 8]
[9 5 1]
[2 7 6]]
[[4 9 2]
[3 5 7]
[8 1 6]]
[[6 1 8]
[7 5 3]
[2 9 4]]
[[6 7 2]
[1 5 9]
[8 3 4]]
[[8 1 6]
[3 5 7]
[4 9 2]]
[[8 3 4]
[1 5 9]
[6 7 2]]全排列（非递归）
标准库itertools里提供了排列的函数，算法比较复杂j就不研究了，顺便还有组合的函数：
import itertools
>>> list(itertools.permutations([1, 2, 3], 3))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
>>> list(itertools.combinations([1, 2, 3], 2))
[(1, 2), (1, 3), (2, 3)]计算还是一样的：
>>> li = [i+1 for i in range(9)]
>>> for i in itertools.permutations(li, 9):
a = np.array(i).reshape(3, 3)
if is_lo_shu_square(a):
print(a)
[[2 7 6]
[9 5 1]
[4 3 8]]
[[2 9 4]
[7 5 3]
[6 1 8]]
[[4 3 8]
[9 5 1]
[2 7 6]]
[[4 9 2]
[3 5 7]
[8 1 6]]
[[6 1 8]
[7 5 3]
[2 9 4]]
[[6 7 2]
[1 5 9]
[8 3 4]]
[[8 1 6]
[3 5 7]
[4 9 2]]
[[8 3 4]
[1 5 9]
[6 7 2]]整个计算过程的执行时间大致是从8秒提高到了6秒。时间上没有本质的区别，并且如果要去计算更大的列表的全排列，比如16个元素的，两种算法都是执行不完的。
不过非递归算法节省内存，整个过程中内存的分配不会有大的变化。而递归算法对内存的开销是巨大的。
16宫格
上面的算法虽然也支持计算16宫格，但是算法复杂度太高，至少我的电脑上运行不出结果来。第一步16个元素的全排列就计算不完，2亿亿次（16! = 20,922,789,888,000）。
很明显有些情况计算之后就能排除很多类似的情况。
数字分组（行的和相等）
先把16个数，分成4组，每组的和都相等，这就是将来每行的数字的集合：
def square_list(d):
"""选项4组数组，每组数组组成一行，并且和相等
返回所有行的和都符合的二维元祖
"""
nums = [i + 1 for i in range(d * d)]
sum_line = sum(nums) // d
# lines = itertools.combinations(nums, d) # 4阶共有1820个
lines = (i for i in itertools.combinations(nums, d) if sum(i) == sum_line) # 筛选后4阶共有86个
for square in itertools.combinations(lines, d):
s = set()
for line in square:
for n in line:
s.add(n)
if len(s) == d*d:
yield square # 4阶共有392个这步能筛选出392种组合等待续操作。
调整每行的元素排列（列的行相等）
把上面的每种组合用下面的方法再做一次遍历。每行的数字互相调整位置，使得每列的和也相等：
def square_list2(square, sum_line=None, skip=0, squares=None):
"""调整每行数字的排列，找到能使每列数字之和也相等的二维元祖
返回的是所有列的和也都符合的二维元祖，
这步之后4阶能筛选出22896个
:param square:
:param sum_line: 第一次递归的时候计算出来
:param skip: 第一次调整第0列，之后递增
:return:
"""
column_count = len(square[0])
if skip >= column_count: # 递归的退出条件
if squares is None:
squares = []
squares.append(square)
return squares
row_count = len(square)
if sum_line is None:
sum_line = sum(square[0])
# 遍历所有的情况，交换元素直到一列的和等于sum_line，
# 然后递归调用处理后面的列，直到处理完所有的列
for li in index_list(row_count, column_count-skip):
sq = [list(i) for i in square]
sum_list = []
for i in range(row_count):
sum_list.append(sq[i][li[i]+skip])
if sum(sum_list) == sum_line:
for j in range(row_count):
sq[j][0+skip], sq[j][li[j]+skip] = sq[j][li[j]+skip], sq[j][0+skip]
sq_tpl = tuple((tuple(i) for i in sq))
squares = square_list2(sq_tpl, sum_line, skip + 1, squares)
return squares
def index_list(lenth, notation):
"""返回一个下标的列表
被square_list2调用，遍历每一行取一个值的所有情况
"""
counter = 0
while True:
n = counter
li = []
for i in range(lenth):
n, index = divmod(n, notation)
li.append(index)
if n == 0:
yield li[::-1]
counter += 1
else:
break这里用了递归。另外遍历下标的index_list函数用了取模取余的方式，做的是类似10进制转4进制，然后每一位就是一个下标，最后把列表反转之后返回了。
最后一个筛选出22896个数组，每个都是行和列的和都相等的。
调整行之间的排序（斜线相等）
这步不做计算了，只是遍历。一个4行调整行之间的排列，一共是24种排列，也就是之前的基础上的24倍的量，还是可以接受的。这里就是4个元素的全排列了：
def square_list3(square):
"""调整行与行之间的排列顺序，
4阶的全排列是24种情况，所以会再多24倍数的情况要遍历
每行以及每列的和都相等了，这样调整会影响到斜线计算的结果"""
return itertools.permutations(square, 4)验证函数
之前已经把可能符合条件的数组筛选到五十多万个了，这里只要再写一个函数做最终的验证就能把结果筛选出来了。这里要验证行的和、列的和、斜线的和。斜线的和不只是对角线，每个方向4条斜线一共8条斜线。另外再验证4个角和中心4块的和，不过这2步不影响结果，行和列是之前的筛选条件，也不影响结果，只是验证结果正确。只要是通过斜线的计算把不符合的再筛掉一批：
def is_lo_shu_square4(arr):
"""接收numpy的二维数组"""
if np.shape(arr)[0] != np.shape(arr)[1]:
return False
d = np.shape(arr)[0]
n = np.sum(arr) / d
for i in np.sum(arr, axis=0):
if i != n:
return False
for i in np.sum(arr, axis=1):
if i != n:
return False
# 检查所有的斜线，包括对角线
for i in range(d):
if np.sum((np.eye(d, k=i, dtype=int) + np.eye(d, k=i-d, dtype=int)) * arr) != n:
return False
if np.sum((np.eye(d, k=i, dtype=int)[::-1] + np.eye(d, k=i-d, dtype=int)[::-1]) * arr) != n:
return False
# 到此能找到384个
# 检查4个角的4个数的和也要符合要求，不影响结果
if np.sum(arr[:2, :2]) != n:
return False
if np.sum(arr[:2, -2:]) != n:
return False
if np.sum(arr[-2:, :2]) != n:
return False
if np.sum(arr[-2:, -2:]) != n:
return False
# 在检查最中间的4个格子的和，不影响结果
if np.sum(arr[1:3, 1:3]) != n:
return False
return True48个完美解
所有符合要求的数组一共384个，这里只输出(0, 0)和(1, 1)的位置上是1的48个数组：
def main():
count = 0
for square in square_list(4):
# 有可能返回空，因为不是每一种组合都一定能得到竖排和相等的矩阵
squares2 = square_list2(square)
if squares2:
for square2 in squares2:
for square3 in square_list3(square2):
a = np.array(square3)
if is_lo_shu_square4(a):
if a[0][0] == 1 or a[1][1] == 1:
count += 1
print(a)
print(count)下面贴上所有的48个数组，其他的数组只是这个基础上的转置和双奇双偶变换（把数组横向或纵向位移2个单位）的结果：
[[ 1 14 4 15]
[ 8 11 5 10]
[13 2 16 3]
[12 7 9 6]]
[[ 1 14 4 15]
[12 7 9 6]
[13 2 16 3]
[ 8 11 5 10]]
[[ 1 15 4 14]
[ 8 10 5 11]
[13 3 16 2]
[12 6 9 7]]
[[ 1 15 4 14]
[12 6 9 7]
[13 3 16 2]
[ 8 10 5 11]]
[[11 8 10 5]
[14 1 15 4]
[ 7 12 6 9]
[ 2 13 3 16]]
[[ 7 12 6 9]
[14 1 15 4]
[11 8 10 5]
[ 2 13 3 16]]
[[10 8 11 5]
[15 1 14 4]
[ 6 12 7 9]
[ 3 13 2 16]]
[[ 6 12 7 9]
[15 1 14 4]
[10 8 11 5]
[ 3 13 2 16]]
[[ 1 12 6 15]
[ 8 13 3 10]
[11 2 16 5]
[14 7 9 4]]
[[ 1 12 6 15]
[14 7 9 4]
[11 2 16 5]
[ 8 13 3 10]]
[[ 1 15 6 12]
[ 8 10 3 13]
[11 5 16 2]
[14 4 9 7]]
[[ 1 15 6 12]
[14 4 9 7]
[11 5 16 2]
[ 8 10 3 13]]
[[13 8 10 3]
[12 1 15 6]
[ 7 14 4 9]
[ 2 11 5 16]]
[[ 7 14 4 9]
[12 1 15 6]
[13 8 10 3]
[ 2 11 5 16]]
[[10 8 13 3]
[15 1 12 6]
[ 4 14 7 9]
[ 5 11 2 16]]
[[ 4 14 7 9]
[15 1 12 6]
[10 8 13 3]
[ 5 11 2 16]]
[[ 1 12 7 14]
[ 8 13 2 11]
[10 3 16 5]
[15 6 9 4]]
[[ 1 12 7 14]
[15 6 9 4]
[10 3 16 5]
[ 8 13 2 11]]
[[ 1 14 7 12]
[ 8 11 2 13]
[10 5 16 3]
[15 4 9 6]]
[[ 1 14 7 12]
[15 4 9 6]
[10 5 16 3]
[ 8 11 2 13]]
[[13 8 11 2]
[12 1 14 7]
[ 6 15 4 9]
[ 3 10 5 16]]
[[ 6 15 4 9]
[12 1 14 7]
[13 8 11 2]
[ 3 10 5 16]]
[[11 8 13 2]
[14 1 12 7]
[ 4 15 6 9]
[ 5 10 3 16]]
[[ 4 15 6 9]
[14 1 12 7]
[11 8 13 2]
[ 5 10 3 16]]
[[ 1 8 10 15]
[12 13 3 6]
[ 7 2 16 9]
[14 11 5 4]]
[[ 1 8 10 15]
[14 11 5 4]
[ 7 2 16 9]
[12 13 3 6]]
[[ 1 15 10 8]
[12 6 3 13]
[ 7 9 16 2]
[14 4 5 11]]
[[ 1 15 10 8]
[14 4 5 11]
[ 7 9 16 2]
[12 6 3 13]]
[[13 12 6 3]
[ 8 1 15 10]
[11 14 4 5]
[ 2 7 9 16]]
[[11 14 4 5]
[ 8 1 15 10]
[13 12 6 3]
[ 2 7 9 16]]
[[ 6 12 13 3]
[15 1 8 10]
[ 4 14 11 5]
[ 9 7 2 16]]
[[ 4 14 11 5]
[15 1 8 10]
[ 6 12 13 3]
[ 9 7 2 16]]
[[ 1 8 11 14]
[12 13 2 7]
[ 6 3 16 9]
[15 10 5 4]]
[[ 1 8 11 14]
[15 10 5 4]
[ 6 3 16 9]
[12 13 2 7]]
[[ 1 14 11 8]
[12 7 2 13]
[ 6 9 16 3]
[15 4 5 10]]
[[ 1 14 11 8]
[15 4 5 10]
[ 6 9 16 3]
[12 7 2 13]]
[[13 12 7 2]
[ 8 1 14 11]
[10 15 4 5]
[ 3 6 9 16]]
[[10 15 4 5]
[ 8 1 14 11]
[13 12 7 2]
[ 3 6 9 16]]
[[ 7 12 13 2]
[14 1 8 11]
[ 4 15 10 5]
[ 9 6 3 16]]
[[ 4 15 10 5]
[14 1 8 11]
[ 7 12 13 2]
[ 9 6 3 16]]
[[ 1 8 13 12]
[14 11 2 7]
[ 4 5 16 9]
[15 10 3 6]]
[[ 1 8 13 12]
[15 10 3 6]
[ 4 5 16 9]
[14 11 2 7]]
[[ 1 12 13 8]
[14 7 2 11]
[ 4 9 16 5]
[15 6 3 10]]
[[ 1 12 13 8]
[15 6 3 10]
[ 4 9 16 5]
[14 7 2 11]]
[[11 14 7 2]
[ 8 1 12 13]
[10 15 6 3]
[ 5 4 9 16]]
[[10 15 6 3]
[ 8 1 12 13]
[11 14 7 2]
[ 5 4 9 16]]
[[ 7 14 11 2]
[12 1 8 13]
[ 6 15 10 3]
[ 9 4 5 16]]
[[ 6 15 10 3]
[12 1 8 13]
[ 7 14 11 2]
[ 9 4 5 16]]16宫格的完美解：
将16个自然数1至16填入16宫格中，是4横、4竖、8斜的4数之和相等，且等于组成14个正方形的4个顶点的数之和（这个没验证）。共48个解。
完美解的16宫格模型如下：
当年奥数教的16宫格还不是这里的完美解：
小结
用到了很多零碎的知识：
- 排列、组合
- 递归（比较搞脑筋）
- 取模、取余（用着不难，关键是要想到用这个方法来遍历所有下标的情况来解决问题）
- 列表的反转（这个算是小技巧）
- 次对角线全1的矩阵（做一次反转即可）
- 二维数组转90度（还是列表反转的技巧，反转加转置后就是，这里没用到）
- 线性代数（只是简单的用乘法算一下对角线上的数字之和）
- 16宫格的48个完美解（当年老师奥数只教了1种）
新闻名称：九宫格问题、16宫格
本文地址：http://scyanting.com/article/jcjshg.html
