Scippy

    SCIP

    Solving Constraint Integer Programs

    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-2026 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 */