Generated on for Gecode by doxygen 1.17.0
sudoku.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 * Guido Tack <tack@gecode.dev>
6 * Christian Schulte <schulte@gecode.dev>
7 *
8 * Copyright:
9 * Mikael Zayenz Lagerkvist, 2005
10 * Guido Tack, 2005
11 * Christian Schulte, 2005
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.dev
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#include <gecode/driver.hh>
39#include <gecode/int.hh>
40#include <gecode/minimodel.hh>
41
42#include <string>
43#include <cmath>
44#include <cctype>
45#include <cstring>
46
47using namespace Gecode;
48
50
62class Sudoku : public Script {
63protected:
65 int nn;
68public:
69
71 Sudoku(const InstanceOptions& opt) : Script(opt) {
72 SudokuInstance si(opt);
73 nn = si.nn;
74 x = IntVarArray(*this, nn*nn, 1, nn);
76
77 // Constraints for rows and columns
78 for (int i=0; i<nn; i++) {
79 distinct(*this, m.row(i), opt.ipl());
80 distinct(*this, m.col(i), opt.ipl());
81 }
82
83 // Constraints for boxes
84 for (int i=0; i<nn; i+=si.bw) {
85 for (int j=0; j<nn; j+=si.bh) {
86 distinct(*this, m.slice(i, i+si.bw, j, j+si.bh), opt.ipl());
87 }
88 }
89
90 // Fill-in predefined fields
91 for (int i=0; i<nn; i++)
92 for (int j=0; j<nn; j++)
93 if (int v = si.givens[j*nn+i])
94 rel(*this, m(i,j), IRT_EQ, v );
95
96 branch(*this, x, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
97 }
98
100 Sudoku(Sudoku& s) : Script(s), nn(s.nn) {
101 x.update(*this, s.x);
102 }
103
105 virtual Space*
106 copy(void) {
107 return new Sudoku(*this);
108 }
109
111 virtual void
112 print(std::ostream& os) const {
113 os << " ";
114 for (int i = 0; i<nn*nn; i++) {
115 if (x[i].assigned()) {
116 print_value(os, x[i].val());
117 os << " ";
118 }
119 else
120 os << ". ";
121 if((i+1)%nn == 0)
122 os << std::endl << " ";
123 }
124 os << std::endl;
125 }
126
127};
128
132int
133main(int argc, char* argv[]) {
134 InstanceOptions opt("Sudoku", instance_spec);
135 opt.instance("0");
136 opt.ipl(IPL_DOM);
137 opt.solutions(1);
138 opt.parse(argc,argv);
139 try {
140 if (!SudokuInstance(opt).valid()) {
141 std::cerr << "Error: instance must be a number between 0 and " << n_examples-1 << " or a file" << std::endl;
142 return 1;
143 }
144 } catch (const Instance::Error& e) {
145 std::cerr << e.what() << std::endl;
146 return 1;
147 }
149 return 0;
150}
151
152// STATISTICS: example-any
static void run(const Options &opt, Script *s=nullptr)
Options for scripts with additional instance parameter
Definition driver.hh:834
Exception for errors in specs and instance files
Definition instance.hh:337
virtual const char * what(void) const noexcept override
Return the full message.
Definition data.cpp:56
Integer variable array.
Definition int.hh:792
Matrix-interface for arrays.
Slice< A > slice(int fc, int tc, int fr, int tr) const
Access slice of the matrix.
Definition matrix.hpp:171
Slice< A > col(int c) const
Access column c.
Definition matrix.hpp:183
Slice< A > row(int r) const
Access row r.
Definition matrix.hpp:177
Computation spaces.
Definition core.hpp:1787
Base class for Sudoku puzzles.
Sudoku(const InstanceOptions &opt)
Constructor.
Definition sudoku.cpp:71
void print_value(std::ostream &os, int v)
Print value v of a field, with the symbols of the scaled sudoku corpus.
int nn
The side of the grid.
virtual Space * copy(void)
Perform copying during cloning.
Definition sudoku.cpp:106
IntVarArray x
Values for the fields.
Definition sudoku.cpp:67
virtual void print(std::ostream &os) const
Print solution.
Definition sudoku.cpp:112
Sudoku(Sudoku &s)
Constructor for cloning s.
Definition sudoku.cpp:100
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:177
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:1002
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_EQ
Equality ( ).
Definition int.hh:1226
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:1279
int main(void)
Definition main.cpp:15
bool valid(const FloatVal &n)
Return whether float n is a valid number.
Definition limits.hpp:39
Gecode toplevel namespace
IntVarBranch INT_VAR_AFC_SIZE_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count divided by domain size with decay factor d.
Definition var.hpp:236
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
Options opt
The options.
Definition test.cpp:163