如何用整数线性规划高效求解4×4零和幻方重排问题

4×4零和幻方是指4行4列的方阵，其中填入1到16的整数，每行、每列、两条主对角线的数字之和都等于34，重排问题即寻找所有满足该条件的不同排列形式。整数线性规划通过定义整数决策变量、目标函数和线性约束，能系统化地求解这类组合优化问题，避免暴力枚举的冗余计算。

问题建模基础

首先需要明确4×4零和幻方的核心约束条件，所有约束都可以转化为线性等式，适合用整数线性规划处理。核心约束包含三类：

• 每个数字1到16在方阵中恰好出现一次
• 每行4个数字之和等于34
• 每列4个数字之和等于34
• 两条主对角线数字之和等于34

整数线性规划模型定义

决策变量定义

我们定义二元决策变量x_{i,j,k}，其中i表示行号（1到4），j表示列号（1到4），k表示数字（1到16）。x_{i,j,k}=1表示第i行第j列填入数字k，否则为0。

约束条件转化

将幻方的规则转化为线性约束：

1. 每个位置只能填一个数字：

   # 对每个i,j，所有k的x_{i,j,k}之和为1
   for i in range(1,5):
       for j in range(1,5):
           sum(x[i][j][k] for k in range(1,17)) == 1
   

2. 每个数字只能出现一次：

   # 对每个k，所有i,j的x_{i,j,k}之和为1
   for k in range(1,17):
       sum(x[i][j][k] for i in range(1,5) for j in range(1,5)) == 1
   

3. 行和约束：

   # 每行数字和为34
   for i in range(1,5):
       sum(k * x[i][j][k] for j in range(1,5) for k in range(1,17)) == 34
   

4. 列和约束：

   # 每列数字和为34
   for j in range(1,5):
       sum(k * x[i][j][k] for i in range(1,5) for k in range(1,17)) == 34
   

5. 对角线约束：

   # 主对角线（i=j）和为34
   sum(k * x[i][i][k] for i in range(1,5) for k in range(1,17)) == 34
   # 副对角线（i+j=5）和为34
   sum(k * x[i][5-i][k] for i in range(1,5) for k in range(1,17)) == 34
   

目标函数

由于我们需要枚举所有可行解，不需要优化特定目标，因此可以设置目标函数为常数0，求解器会返回所有满足约束的可行解。

求解实现示例

使用Python的pulp库实现上述模型，完整代码如下：

import pulp

# 初始化问题
prob = pulp.LpProblem("4x4_Magic_Square", pulp.LpMinimize)
# 定义决策变量，x[i][j][k] 表示第i行第j列是否为数字k
x = {}
for i in range(1,5):
    for j in range(1,5):
        for k in range(1,17):
            x[(i,j,k)] = pulp.LpVariable(f"x_{i}_{j}_{k}", cat='Binary')

# 目标函数设为0
prob += 0

# 约束1：每个位置只能填一个数字
for i in range(1,5):
    for j in range(1,5):
        prob += pulp.lpSum(x[(i,j,k)] for k in range(1,17)) == 1

# 约束2：每个数字只能出现一次
for k in range(1,17):
    prob += pulp.lpSum(x[(i,j,k)] for i in range(1,5) for j in range(1,5)) == 1

# 约束3：行和等于34
for i in range(1,5):
    prob += pulp.lpSum(k * x[(i,j,k)] for j in range(1,5) for k in range(1,17)) == 34

# 约束4：列和等于34
for j in range(1,5):
    prob += pulp.lpSum(k * x[(i,j,k)] for i in range(1,5) for k in range(1,17)) == 34

# 约束5：主对角线和等于34
prob += pulp.lpSum(k * x[(i,i,k)] for i in range(1,5) for k in range(1,17)) == 34

# 约束6：副对角线和等于34
prob += pulp.lpSum(k * x[(i,5-i,k)] for i in range(1,5) for k in range(1,17)) == 34

# 求解问题
prob.solve(pulp.PULP_CBC_CMD(msg=False))

# 输出结果
if pulp.LpStatus[prob.status] == 'Optimal':
    square = [[0 for _ in range(4)] for _ in range(4)]
    for i in range(1,5):
        for j in range(1,5):
            for k in range(1,17):
                if pulp.value(x[(i,j,k)]) == 1:
                    square[i-1][j-1] = k
    print("找到的4x4零和幻方：")
    for row in square:
        print(row)
else:
    print("未找到可行解")

效率对比

传统暴力枚举的时间复杂度为16!，约为2e13量级，几乎无法在合理时间内完成计算。而整数线性规划通过约束剪枝，将搜索空间大幅缩小，在普通个人电脑上可以在几秒内得到所有合法解，效率提升非常明显。

总结

整数线性规划通过将4×4零和幻方的重排规则转化为线性约束，能够高效求解这类组合优化问题。相比暴力枚举，它不需要遍历所有排列，而是通过数学约束快速排除不符合条件的解，是处理类似排列约束问题的有效方法。开发者可以根据实际需求调整约束条件，适配不同规格的幻方求解场景。

整数线性规划零和幻方4×4幻方重排问题修改时间：2026-07-21 21:24:32