对数独问题建模,用Gurobi/COPT/CPLEX求解,得到的可行解必须满 足:第一个数 = 你的学号 的最后一位数;尾号为0的同学 可任意设定,请给出代码
时间: 2024-06-09 17:04:37 浏览: 13
这个问题可以通过整数规划(Integer Programming)来建模求解。首先,我们需要定义变量和约束条件。
变量:
- $x_{i,j,k}$:表示数独中第 $i$ 行、第 $j$ 列填入数字 $k$ 的可行性,$k$ 取值范围为 $1$ 到 $9$。
约束条件:
- 每个格子只能填入一个数字:$\sum\limits_{k=1}^9 x_{i,j,k} = 1$,其中 $i,j$ 分别表示行和列。
- 每个行、列、宫内都不能出现重复数字:$\sum\limits_{i=1}^9 x_{i,j,k} = 1$,$\sum\limits_{j=1}^9 x_{i,j,k} = 1$,$\sum\limits_{i'=3p+1}^{3p+3}\sum\limits_{j'=3q+1}^{3q+3} x_{i',j',k} = 1$,其中 $p,q$ 分别表示宫的行和列。
- 已知数字的格子的可行性:$x_{i,j,k} = 1$,其中 $(i,j)$ 表示已知数字的位置,$k$ 表示已知数字的值。
- 第一个数等于学号的最后一位数:$x_{1,1,k} = 1$,其中 $k$ 等于学号的最后一位数。
- 尾号为0的同学可以任意设定:无需添加约束条件。
根据以上定义,可以得到如下的整数规划模型:
$$
\begin{aligned}
\min_{x_{i,j,k}} 0 \\
\text{s.t.} \quad & \sum\limits_{k=1}^9 x_{i,j,k} = 1, \quad \forall i,j \\
& \sum\limits_{i=1}^9 x_{i,j,k} = 1, \quad \forall j,k \\
& \sum\limits_{j=1}^9 x_{i,j,k} = 1, \quad \forall i,k \\
& \sum\limits_{i'=3p+1}^{3p+3}\sum\limits_{j'=3q+1}^{3q+3} x_{i',j',k} = 1, \quad \forall p,q,k \\
& x_{i,j,k} = 1, \quad \text{if $(i,j)$ is given and equals $k$} \\
& x_{1,1,k} = 1, \quad \text{if $k$ equals the last digit of your student ID} \\
& x_{i,j,k} \in \{0,1\}, \quad \forall i,j,k
\end{aligned}
$$
下面是用 Gurobi 求解的 Python 代码:
```python
import gurobipy as gp
# 数独谜题,0 表示未知数字
puzzle = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]
]
# 学号的最后一位数
last_digit = int(input("请输入学号的最后一位数:"))
# 创建模型
m = gp.Model()
# 创建变量
x = {}
for i in range(9):
for j in range(9):
for k in range(1, 10):
x[i, j, k] = m.addVar(vtype=gp.GRB.BINARY, name=f"x_{i}_{j}_{k}")
# 每个格子只能填入一个数字
for i in range(9):
for j in range(9):
m.addConstr(gp.quicksum(x[i, j, k] for k in range(1, 10)) == 1)
# 每个行、列、宫内都不能出现重复数字
for i in range(9):
for k in range(1, 10):
m.addConstr(gp.quicksum(x[i, j, k] for j in range(9)) == 1)
for k in range(1, 10):
m.addConstr(gp.quicksum(x[i, j, k] for i in range(9)) == 1)
for p in range(3):
for q in range(3):
m.addConstr(gp.quicksum(x[3*p+i, 3*q+j, k] for i in range(3) for j in range(3)) == 1)
# 已知数字的格子的可行性
for i in range(9):
for j in range(9):
if puzzle[i][j] != 0:
m.addConstr(x[i, j, puzzle[i][j]] == 1)
# 第一个数等于学号的最后一位数
m.addConstr(x[0, 0, last_digit] == 1)
# 求解模型
m.optimize()
# 输出结果
if m.status == gp.GRB.OPTIMAL:
for i in range(9):
for j in range(9):
for k in range(1, 10):
if x[i, j, k].x > 0.5:
print(k, end=" ")
print()
else:
print("无解")
```
需要注意的是,上述代码中的 `input` 函数用于从控制台读取学号的最后一位数,需要手动输入。