对数独问题建模,用Gurobi/COPT/CPLEX求解,得到的可行解必须满 足:第一个数 = 你的学号 的最后一位数;尾号为0的同学 可任意设定,请给出C++代码
时间: 2024-05-13 15:16:39 浏览: 50
基于C++实现数独【100012553】
以下是用Gurobi求解数独问题并满足条件的C++代码:
```c++
#include <iostream>
#include <vector>
#include "gurobi_c++.h"
using namespace std;
const int N = 9; // 数独的大小为9x9
const int M = 3; // 每个小宫格的大小为3x3
int student_id = 123456789; // 学号
int last_num = student_id % 10; // 学号的最后一位数
// 数独题目,0表示空格
int puzzle[N][N] = {
{0, 0, 0, 0, 2, 0, 0, 0, 9},
{0, 0, 0, 7, 0, 0, 0, 0, 3},
{0, 6, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 5, 0},
{0, 0, 0, 0, 0, 0, 4, 0, 0},
{9, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 7, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0}
};
void solveSudoku() {
try {
GRBEnv env = GRBEnv();
GRBModel model = GRBModel(env);
// 定义决策变量
GRBVar x[N][N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
x[i][j][k] = model.addVar(0.0, 1.0, 0.0, GRB_BINARY);
}
}
}
// 每个格子只能填一个数
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
GRBLinExpr expr = 0;
for (int k = 0; k < N; k++) {
expr += x[i][j][k];
}
model.addConstr(expr == 1);
}
}
// 每行每列每宫格中每个数字只能出现一次
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
GRBLinExpr expr_row = 0, expr_col = 0, expr_blk = 0;
for (int j = 0; j < N; j++) {
expr_row += x[i][j][k];
expr_col += x[j][i][k];
int blk_row = (i / M) * M + j / M;
int blk_col = (i % M) * M + j % M;
expr_blk += x[blk_row][blk_col][k];
}
model.addConstr(expr_row == 1);
model.addConstr(expr_col == 1);
model.addConstr(expr_blk == 1);
}
}
// 数独初始条件
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (puzzle[i][j] != 0) {
int k = puzzle[i][j] - 1;
model.addConstr(x[i][j][k] == 1);
}
}
}
// 第一个数等于学号的最后一位数
model.addConstr(x[0][0][last_num - 1] == 1);
// 优化
model.optimize();
// 输出结果
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (x[i][j][k].get(GRB_DoubleAttr_X) > 0.5) {
cout << k + 1 << " ";
}
}
}
cout << endl;
}
} catch (GRBException e) {
cout << "Error code = " << e.getErrorCode() << endl;
cout << e.getMessage() << endl;
}
}
int main() {
solveSudoku();
return 0;
}
```
在这个代码中,我们使用了Gurobi来求解数独问题,并添加了一个额外的约束条件,即第一个数必须等于学号的最后一位数。如果学号的最后一位数是0,则可以任意设定第一个数。
注意,在使用上述代码时,需要先安装Gurobi和相应的C++库,并将代码中的学号和数独题目修改为自己的。
阅读全文