SCIP
Solving Constraint Integer Programs
Sudoku Solver
Methodology
To solve the given sudoku puzzle using integer programming, we shall use this handy tutorial; http://profs.sci.univr.it/~rrizzi/classes/PLS2015/sudoku/doc/497_Olszowy_Wiktor_Sudoku.pdf
An unsolved sudoku puzzle looks like below:
+-------—+--------—+--------—+
|* * * | * * * | * * * |
|* 3 * | * 1 2 | * * 8 |
|* 7 * | * 6 8 | * 2 * |
+-------—+--------—+--------—+
|* * * | * * 9 | 8 7 * |
|1 2 * | 6 5 * | 4 * * |
|* * * | * * * | * * 6 |
+-------—+--------—+--------—+
|* * 3 | 9 4 * | * * * |
|* * * | 2 * * | * 6 * |
|4 * * | * * * | * 3 1 |
+-------—+--------—+--------—+
The solved puzzle will have each of the nine rows and columns filled by numbers 1, ..., 9 each appearing exactly once. There are 9 subgrids and each subgrid also needs to be filled by numbers 1, ..., 9 each appearing exactly once. As seen in the unsolved puzzles, some of the positions are already filled.
In this example, we see
- how to model problems with many variables in SCIP,
- how to set parameters
- how use the solution status to print custom output messages.
Data Format
A sudoku puzzle is in represented by a string of 81 charcaters. An already filled number in the puzzle is represented by that number; a blank is represented by either '.' or '0' in the puzzle string. The input file is containing the configuration of a sudoku read rowwise as a string. For example, the above puzzle is represented by 000000000030012008070068020000009870120650400000000006003940000000200060400000031 or ..........3..12..8.7..68.2......987.12.65.4..........6..394.......2...6.4......31
Installation
See the Install file