manbet体育手机客户端

sudoku_c + + . cpp

/*版权所有2018,Gurobi优化狗万app足彩，LLC */ /*数独实例。数独棋盘是一个9x9的网格，再细分为3x3的3x3网格。网格中的每个单元格必须取一个从0到9的值。在同一行、列或3x3子网格中，没有两个网格单元可以取相同的值。在MIP公式中，二进制变量x[i,j,v]表示cell 是否取值'v'。约束条件如下:1。每个单元格必须取一个值(sum_v x[i,j,v] = 1) 2。每个值每一行只使用一次(sum_i x[i,j,v] = 1) 3。每个值在每个列中只使用一次(sum_j x[i,j,v] = 1) 4。每个值在每个3x3子网格中只使用一次(sum_grid x[i,j,v] = 1)。这个例子的输入数据集可以在examples/data/sudoku*中找到。 */ #include "gurobi_c++.h" #include  using namespace std; #define sd 3 #define n (sd*sd) string itos(int i) {stringstream s; s << i; return s.str(); } int main(int argc, char *argv[]) { try { GRBEnv env = GRBEnv(); GRBModel model = GRBModel(env); GRBVar vars[n][n][n]; int i, j, v; // Create 3-D array of model variables for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { for (v = 0; v < n; v++) { string s = "G_" + itos(i) + "_" + itos(j) + "_" + itos(v); vars[i][j][v] = model.addVar(0.0, 1.0, 0.0, GRB_BINARY, s); } } } // Add constraints // Each cell must take one value for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { GRBLinExpr expr = 0; for (v = 0; v < n; v++) expr += vars[i][j][v]; string s = "V_" + itos(i) + "_" + itos(j); model.addConstr(expr, GRB_EQUAL, 1.0, s); } } // Each value appears once per row for (i = 0; i < n; i++) { for (v = 0; v < n; v++) { GRBLinExpr expr = 0; for (j = 0; j < n; j++) expr += vars[i][j][v]; string s = "R_" + itos(i) + "_" + itos(v); model.addConstr(expr == 1.0, s); } } // Each value appears once per column for (j = 0; j < n; j++) { for (v = 0; v < n; v++) { GRBLinExpr expr = 0; for (i = 0; i < n; i++) expr += vars[i][j][v]; string s = "C_" + itos(j) + "_" + itos(v); model.addConstr(expr == 1.0, s); } } // Each value appears once per sub-grid for (v = 0; v < n; v++) { for (int i0 = 0; i0 < sd; i0++) { for (int j0 = 0; j0 < sd; j0++) { GRBLinExpr expr = 0; for (int i1 = 0; i1 < sd; i1++) { for (int j1 = 0; j1 < sd; j1++) { expr += vars[i0*sd+i1][j0*sd+j1][v]; } } string s = "Sub_" + itos(v) + "_" + itos(i0) + "_" + itos(j0); model.addConstr(expr == 1.0, s); } } } // Fix variables associated with pre-specified cells char input[10]; for (i = 0; i < n; i++) { cin >> input; for (j = 0; j < n; j++) { int val = (int) input[j] - 48 - 1; // 0-based if (val >= 0) vars[i][j][val].set(GRB_DoubleAttr_LB, 1.0); } } // Optimize model model.optimize(); // Write model to file model.write("sudoku.lp"); cout << endl; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { for (v = 0; v < n; v++) { if (vars[i][j][v].get(GRB_DoubleAttr_X) > 0.5) cout << v+1; } } cout << endl; } cout << endl; } catch(GRBException e) { cout << "Error code = " << e.getErrorCode() << endl; cout << e.getMessage() << endl; } catch (...) { cout << "Error during optimization" << endl; } return 0; }