Scippy

SCIP

Solving Constraint Integer Programs

sudoku_main.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file sudoku_main.cpp
17  * @brief Sudoku solver built using constrained integer programming
18  * @author Naga V C Gudapati
19 */
20 
21 #include <iostream>
22 #include <sstream>
23 
24 #include "sudoku_utils.h"
25 
26 #include <scip/scip.h>
27 #include <scip/scipdefplugins.h>
28 
29 
30 int main(int argc, char *argv[])
31 {
32  /* declaration of variables used in forloops later on */
33  int i = 0;
34  int j = 0;
35  int k = 0;
36  int p = 0;
37  int q = 0;
38 
39  if( argc < 2 )
40  {
41  std::cerr << "call " << argv[0] << " <puzzle file> " << "\n";
42  exit(1);
43  }
44 
45  std::string puzzlefilepath = argv[1];
46  auto puzzle = sudoku::getSudokuPuzzle(puzzlefilepath);
47  std::cout << "The unsolved Sudoku Puzzle is: " << "\n";
48  sudoku::printSudoku(puzzle);
49 
50  /*
51  * Setting up the SCIP environment
52  */
53  SCIP* scip = nullptr; /* Declaring the scip environment*/
54  SCIP_CALL( SCIPcreate(&scip) ); /*Creating the SCIP environment */
55  SCIP_CALL( SCIPincludeDefaultPlugins(scip) ); /* include default plugins */
56  SCIP_CALL( SCIPcreateProbBasic(scip, "sudoku") ); /* creating the SCIP Problem. */
57 
58  /*
59  * The Sudoku puzzle is a feasibility problem and the objsense can be anything
60  */
62 
63  /*
64  * We have to define 9x9x9 variables. Let x_{ijk} where i = 1...9, j = 1...9 and k = 1..9 be those binary variables.
65  * x_{ijk} is the the binary variable representing the number k (1 or 2 or ... 9) in the ith row and jth column
66  */
67  std::vector<std::vector<std::vector< SCIP_VAR* >>> xvars(9, std::vector<std::vector< SCIP_VAR* >>(9, std::vector< SCIP_VAR* >(9)));
68  std::ostringstream namebuf;
69 
70  for( i = 0; i < 9; ++i )
71  {
72  for( j = 0; j < 9; ++j )
73  {
74  for( k = 0; k < 9; ++k )
75  {
76  SCIP_VAR* var = nullptr;
77  namebuf.str("");
78  namebuf << "x[" << i << "," << j << "," << k << "]";
80  scip, /* SCIP environment */
81  &var, /* reference to the variable */
82  namebuf.str().c_str(), /* name of the variable */
83  0.0, /* lower bound of the variable */
84  1.0, /* upper bound of the variable */
85  1.0, /* obj. coefficient. */
86  SCIP_VARTYPE_BINARY /* variable is binary */
87  ) );
88  SCIP_CALL( SCIPaddVar(scip, var) );
89  xvars[i][j][k] = var;
90  }
91  }
92  }
93 
94  /* for each column j and each number k we must have that only one entry of column j is k; since x_{ijk} is 1
95  * if and only if the i-th entry of the j-th column is k, we can model this requirement with the following linear
96  * constraint:
97  * x_1jk + x_2jk + x_3jk + ... + x_9jk = 1 for each j and k
98  */
99  std::vector< SCIP_CONS* > columnconstraints;
100  for( j = 0; j < 9; ++j )
101  {
102  for( k = 0; k < 9; ++k )
103  {
104  SCIP_CONS* cons = nullptr;
105  namebuf.str("");
106  namebuf << "col_" << j << "_" << k << "]";
107 
108  /* we first create an empty equality constraint (i.e. the lhs and rhs are equal to 1) and then add the
109  * variables
110  */
112  scip,
113  &cons, /* pointer to hold the created constraint */
114  namebuf.str().c_str(), /* name of constraint */
115  0, /* number of nonzeros in the constraint */
116  nullptr, /* array with variables of constraint entries */
117  nullptr, /* array with coefficients of constraint entries */
118  1.0, /* left hand side of constraint */
119  1.0) ); /* right hand side of constraint */
120  for( i = 0; i < 9; ++i )
121  {
122  SCIP_CALL( SCIPaddCoefLinear(scip, cons, xvars[i][j][k], 1.0) );
123  }
124 
125  SCIP_CALL( SCIPaddCons(scip, cons) );
126  columnconstraints.push_back(cons);
127  }
128  }
129 
130  /* for each row i and each number k we must have that only one entry of row i is k; we can model
131  * this requirement with the following linear constraint:
132  * x_i1k + x_i2k + x_i3k + ... + x_i9k = 1 for each i and k
133  */
134  std::vector< SCIP_CONS* > rowconstraints;
135  for( i = 0; i < 9; ++i )
136  {
137  for( k = 0; k < 9; ++k )
138  {
139  SCIP_CONS* cons = nullptr;
140 
141  namebuf.str("");
142  namebuf << "row_" << i << "_" << k << "]";
143 
144  /* we first create an empty equality constraint (i.e. the lhs and rhs are equal to 1) and then add the
145  * variables
146  */
148  scip,
149  &cons, /* pointer to hold the created constraint */
150  namebuf.str().c_str(), /* name of constraint */
151  0, /* number of nonzeros in the constraint */
152  nullptr, /* array with variables of constraint entries */
153  nullptr, /* array with coefficients of constraint entries */
154  1.0, /* left hand side of constraint */
155  1.0) ); /* right hand side of constraint */
156  for( j = 0; j < 9; ++j )
157  {
158  SCIP_CALL( SCIPaddCoefLinear(scip, cons, xvars[i][j][k], 1.0) );
159  }
160 
161  SCIP_CALL( SCIPaddCons(scip, cons) );
162  rowconstraints.push_back(cons);
163  }
164  }
165 
166  /* for each 3x3 subgrid we must we must have that only one entry is k;
167  * a subgrid is formed by the entries (i,j) such that i is in {p, p + 1, p + 2} and j is in {q, q + 1, q + 2} for
168  * each (p, q) in {(1,1), (1,4), (1,7), (4,1), (4, 4), (4, 7), (7, 1), (7, 4), (7, 7)}
169  * for the (p,q)-th subgrid we can model this requirement with the following linear constraint:
170  * sum_{i in [p, p + 2], j in [q, q + 2]} x_ijk = 1 for each k
171  */
172  std::vector< SCIP_CONS* > subgridconstraints;
173  for( k = 0; k < 9; ++k )
174  {
175  for( p = 0; p < 3; ++p )
176  {
177  for( q = 0; q < 3; ++q )
178  {
179  SCIP_CONS* cons = nullptr;
180 
181  namebuf.str("");
182  namebuf << "subgrid_" << k << "_" << p << "_" << q << "]";
183 
184  /* we first create an empty an equality constraint (i.e. the lhs and rhs are equal to 1) and then add the
185  * variables
186  */
188  scip,
189  &cons, /* pointer to hold the created constraint */
190  namebuf.str().c_str(), /* name of constraint */
191  0, /* number of nonzeros in the constraint */
192  nullptr, /* array with variables of constraint entries */
193  nullptr, /* array with coefficients of constraint entries */
194  1.0, /* left hand side of constraint */
195  1.0) ); /* right hand side of constraint */
196 
197  /* since we are using 0 based indexing we should be careful with the loop indices. */
198  for( j = 3 * (p + 1) - 3; j < 3 * (p + 1); ++j )
199  {
200  for( i = 3 * (q + 1) - 3; i < 3 * (q + 1); ++i )
201  {
202  SCIP_CALL( SCIPaddCoefLinear(scip, cons, xvars[i][j][k], 1.0) );
203  }
204  }
205  SCIP_CALL( SCIPaddCons(scip, cons) );
206  subgridconstraints.push_back(cons);
207  }
208  }
209  }
210 
211 
212  /* so far we have required that for each column, row, and subgrid only one occurence of {1, ..., 9} appears.
213  * However, we have not yet imposed that they must appear in different positions. So, for example, a solution
214  * that says that the numbers 3 and 4 appear in entry (1,1) could be feasible.
215  * However, that can only happen if some entry (i,j) has no number assigned to it.
216  * Thus, by requiring that each entry (i,j) has a number assigned to it we obtain a correct model.
217  * This requirement with the following linear constraint:
218  * x_ij1 + x_ij2k + x_ij3 + ... + x_ij9 = 1 for each i and j
219  *
220  */
221  std::vector< SCIP_CONS* > fillgridconstraints;
222  for( i = 0; i < 9; ++i )
223  {
224  for( j = 0; j < 9; ++j )
225  {
226  SCIP_CONS* cons = nullptr;
227 
228  namebuf.str("");
229  namebuf << "fillgrid_" << i << "_" << j << "]";
230 
231  /* we first create an empty an equality constraint (i.e. the lhs and rhs are equal to 1) and then add the
232  * variables
233  */
235  scip,
236  &cons, /* pointer to hold the created constraint */
237  namebuf.str().c_str(), /* name of constraint */
238  0, /* number of nonzeros in the constraint */
239  nullptr, /* array with variables of constraint entries */
240  nullptr, /* array with coefficients of constraint entries */
241  1.0, /* left hand side of constraint */
242  1.0) ); /* right hand side of constraint */
243 
244  for( k = 0; k < 9; ++k )
245  {
246  SCIP_CALL( SCIPaddCoefLinear(scip, cons, xvars[i][j][k], 1.0) );
247  }
248 
249  SCIP_CALL( SCIPaddCons(scip, cons) );
250  fillgridconstraints.push_back(cons);
251  }
252  }
253 
254 
255  /* we use SCIPfixVar to fix the binary variables corresponding to the given value in the puzzle to 1.
256  * see https://www.scipopt.org/doc-7.0.1/html/group__PublicVariableMethods.php#ga7965b16efcb2f8cdf7e289198c5cbe16
257  * for more info
258  */
259  for( i = 0; i < 9; ++i )
260  {
261  for( j = 0; j < 9; ++j )
262  {
263  /* The unsolved puzzle where there are blanks are represented by -1 in the puzzle datastructure */
264  if( puzzle[i][j] > 0 )
265  {
266  SCIP_Bool infeasible;
267  SCIP_Bool fixed;
268 
269  SCIP_CALL( SCIPfixVar(scip, xvars[i][j][puzzle[i][j] - 1], 1.0, &infeasible, &fixed) );
270 
271  assert(fixed == TRUE);
272  /* we are assuming that the puzzle is not instantly infeasible */
273  assert(infeasible == FALSE);
274  }
275  }
276  }
277 
278 
279  /* in c++, we can set the SCIP parameters by <tt> sSCIPsetIntParam(SCIP* scip, "parameter", param_value) ) </tt> */
280  SCIP_CALL( SCIPsetIntParam(scip, "display/verblevel", 0) ); /* turns off the SCIP output */
281  SCIP_CALL( SCIPsolve(scip) );
282 
283  /* Some wrongly generated sudoku puzzles can be infeasible. So we use the solnstatus to display different types of
284  * output.
285  */
286  SCIP_STATUS solutionstatus = SCIPgetStatus( scip );
287 
288  if( solutionstatus == SCIP_STATUS_OPTIMAL )
289  {
290  /* SCIP_STATUS_OPTIMAL status indicates that an optimal solution was found, hence we can print the final puzzle */
291  SCIP_SOL* sol;
292  sol = SCIPgetBestSol( scip );
293 
294  for( i = 0; i < 9; ++i )
295  {
296  for( j = 0; j < 9; ++j )
297  {
298  for( k = 0; k < 9; ++k )
299  {
300  if( SCIPgetSolVal(scip, sol, xvars[i][j][k]) > 0 )
301  {
302  /* As we are using 0 based indices, to display the final puzzle, we should increment values by 1. */
303  puzzle[i][j] = k + 1;
304  }
305  }
306  }
307  }
308  std::cout << "The solved puzzle is: "
309  << "\n";
310  sudoku::printSudoku( puzzle );
311  }
312  else if( solutionstatus == SCIP_STATUS_INFEASIBLE )
313  {
314  /* solutions status of SCIP_STATUS_INFEASIBLE indicates that the puzzle is infeasible. */
315  std::cout << "Check the Input puzzle"
316  << "\n";
317  }
318  else
319  {
320  std::cerr << "Something went wrong during the optimization." << "\n";
321  exit(1);
322  }
323 
324  /*freeing the variables */
325  for( i = 0; i < 9; ++i )
326  {
327  for( j = 0; j < 9; ++j )
328  {
329  for( k = 0; k < 9; ++k )
330  {
331  SCIP_CALL( SCIPreleaseVar(scip, &xvars[i][j][k]) );
332  }
333  }
334  }
335  xvars.clear();
336 
337  /* freeing the constraints
338  * we use C++11's auto keyword to iterate over the constraints and free them.
339  */
340  for( auto &constr : columnconstraints )
341  {
342  SCIP_CALL( SCIPreleaseCons(scip, &constr) );
343  }
344  columnconstraints.clear();
345 
346  for( auto &constr : rowconstraints )
347  {
348  SCIP_CALL( SCIPreleaseCons(scip, &constr) );
349  }
350  rowconstraints.clear();
351 
352  for( auto &constr : subgridconstraints )
353  {
354  SCIP_CALL( SCIPreleaseCons(scip, &constr) );
355  }
356  subgridconstraints.clear();
357 
358  for( auto &constr : fillgridconstraints )
359  {
360  SCIP_CALL( SCIPreleaseCons(scip, &constr) );
361  }
362  fillgridconstraints.clear();
363 
364  /*freeing scip */
365 
366  SCIP_CALL( SCIPfree(&scip) );
367 }
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
#define FALSE
Definition: def.h:87
#define TRUE
Definition: def.h:86
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:185
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:171
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1241
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2613
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2769
std::vector< std::vector< int > > getSudokuPuzzle(std::string &filepath)
Definition: sudoku_utils.h:34
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:474
#define SCIP_CALL(x)
Definition: def.h:384
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:58
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
int main(int argc, char *argv[])
Definition: sudoku_main.cpp:30
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8273
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1667
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
A set of utilities that are used to read the puzzle and display the puzzle.
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
default SCIP plugins
void printSudoku(const std::vector< std::vector< int >> &sudokupuzzle)
Definition: sudoku_utils.h:79
SCIP callable library.
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315