SCIP Doxygen Documentation
Loading...
Searching...
No Matches
xternal_sudoku.c
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-2025 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 examples/Sudoku/doc/xternal_sudoku.c
26
* @brief main document page
27
* @author Naga V C Gudapati
28
*/
29
30
/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31
32
/**@page SUDOKU_MAIN Sudoku Solver
33
* @author Naga V C Gudapati
34
*
35
* Methodology
36
* ============
37
*
38
* To solve the given sudoku puzzle using integer programming, we shall use this handy tutorial;
39
* http://profs.sci.univr.it/~rrizzi/classes/PLS2015/sudoku/doc/497_Olszowy_Wiktor_Sudoku.pdf
40
*
41
* An unsolved sudoku puzzle looks like below:<br>
42
* <tt>
43
* +----------+-----------+-----------+ <br>
44
* |* * * | * * * | * * * | <br>
45
* |* 3 * | * 1 2 | * * 8 | <br>
46
* |* 7 * | * 6 8 | * 2 * | <br>
47
* +----------+-----------+-----------+ <br>
48
* |* * * | * * 9 | 8 7 * | <br>
49
* |1 2 * | 6 5 * | 4 * * | <br>
50
* |* * * | * * * | * * 6 | <br>
51
* +----------+-----------+-----------+ <br>
52
* |* * 3 | 9 4 * | * * * | <br>
53
* |* * * | 2 * * | * 6 * | <br>
54
* |4 * * | * * * | * 3 1 | <br>
55
* +----------+-----------+-----------+ <br>
56
* </tt>
57
*
58
* The solved puzzle will have each of the nine rows and columns filled by numbers 1, ..., 9 each appearing
59
* exactly once. There are 9 subgrids and each subgrid also needs to be filled by numbers 1, ..., 9 each
60
* appearing exactly once. As seen in the unsolved puzzles, some of the positions are already filled.
61
*
62
* In this example, we see
63
* - how to model problems with many variables in SCIP,
64
* - how to set parameters
65
* - how use the solution status to print custom output messages.
66
*
67
* Data Format
68
* ============
69
*
70
* A sudoku puzzle is in represented by a string of 81 charcaters. An already filled number in the
71
* puzzle is represented by that number; a blank is represented by either '.' or '0' in the puzzle
72
* string.
73
* The input file is containing the configuration of a sudoku read rowwise as a string.
74
* For example, the above puzzle is represented by
75
* 000000000030012008070068020000009870120650400000000006003940000000200060400000031
76
* or
77
* ..........3..12..8.7..68.2......987.12.65.4..........6..394.......2...6.4......31
78
*
79
* Installation
80
* ============
81
*
82
* See the @ref INSTALL_APPLICATIONS_EXAMPLES "Install file"
83
*
84
*/
examples
Sudoku
doc
xternal_sudoku.c
© 2002-2025 by Zuse Institute Berlin (ZIB),
Imprint
Generated by
1.13.2