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