sudoku-advanced.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Mikael Lagerkvist <lagerkvist@gecode.org>
* Guido Tack <tack@gecode.org>
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Mikael Lagerkvist, 2005
* Guido Tack, 2005
* Christian Schulte, 2005
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
#ifdef GECODE_HAS_SET_VARS
#include <gecode/set.hh>
#endif
#include <string>
#include <cmath>
#include <cctype>
using namespace Gecode;
#include "examples/sudoku-instances.hh"
class Sudoku : public Script {
protected:
const int n;
public:
#ifdef GECODE_HAS_SET_VARS
enum {
MODEL_INT,
MODEL_SET,
MODEL_MIXED
};
#endif
// Branching variants
enum {
BRANCH_NONE,
BRANCH_SIZE,
BRANCH_SIZE_DEGREE,
BRANCH_SIZE_AFC,
BRANCH_AFC
};
Sudoku(const SizeOptions& opt)
: Script(opt),
n(example_size(examples[opt.size()])) {}
Sudoku(Sudoku& s) : Script(s), n(s.n) {}
};
class SudokuInt : virtual public Sudoku {
protected:
IntVarArray x;
public:
#ifdef GECODE_HAS_SET_VARS
enum {
PROP_NONE,
PROP_SAME,
};
#endif
SudokuInt(const SizeOptions& opt)
: Sudoku(opt), x(*this, n*n*n*n, 1, n*n) {
const int nn = n*n;
Matrix<IntVarArray> m(x, nn, nn);
// Constraints for rows and columns
for (int i=0; i<nn; i++) {
distinct(*this, m.row(i), opt.ipl());
distinct(*this, m.col(i), opt.ipl());
}
// Constraints for squares
for (int i=0; i<nn; i+=n) {
for (int j=0; j<nn; j+=n) {
distinct(*this, m.slice(i, i+n, j, j+n), opt.ipl());
}
}
// Fill-in predefined fields
for (int i=0; i<nn; i++)
for (int j=0; j<nn; j++)
if (int v = sudokuField(examples[opt.size()], nn, i, j))
rel(*this, m(i,j), IRT_EQ, v );
#ifdef GECODE_HAS_SET_VARS
if (opt.propagation() == PROP_SAME) {
// Implied constraints linking squares and rows
for (int b=0; b<n; b++) {
int b1c = 0;
int b2c = 0;
IntVarArgs bc1(nn-n);
IntVarArgs bc2(nn-n);
IntVarArgs br1(nn-n);
IntVarArgs br2(nn-n);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) {
b1c = 0; b2c = 0;
for (int k=0; k<n; k++) {
if (k != j) {
IntVarArgs bc1s = block_col(m, b, i, k);
IntVarArgs br1s = block_row(m, b, i, k);
for (int count=0; count<n; count++) {
bc1[b1c] = bc1s[count];
br1[b1c] = br1s[count];
++b1c;
}
}
if (k != i) {
IntVarArgs bc2s = block_col(m, b, k, j);
IntVarArgs br2s = block_row(m, b, k, j);
for (int count=0; count<n; count++) {
bc2[b2c] = bc2s[count];
br2[b2c] = br2s[count];
++b2c;
}
}
}
same(*this, nn, bc1, bc2);
same(*this, nn, br1, br2);
}
}
}
#endif
if (opt.branching() == BRANCH_NONE) {
branch(*this, x, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
} else if (opt.branching() == BRANCH_SIZE) {
branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_SPLIT_MIN());
} else if (opt.branching() == BRANCH_SIZE_DEGREE) {
branch(*this, x, INT_VAR_DEGREE_SIZE_MAX(), INT_VAL_SPLIT_MIN());
} else if (opt.branching() == BRANCH_SIZE_AFC) {
branch(*this, x, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_SPLIT_MIN());
} else if (opt.branching() == BRANCH_AFC) {
branch(*this, x, INT_VAR_AFC_MAX(opt.decay()), INT_VAL_SPLIT_MIN());
}
}
SudokuInt(SudokuInt& s) : Sudoku(s) {
x.update(*this, s.x);
}
virtual Space*
copy(void) {
return new SudokuInt(*this);
}
virtual void
print(std::ostream& os) const {
os << " ";
for (int i = 0; i<n*n*n*n; i++) {
if (x[i].assigned()) {
if (x[i].val()<10)
os << x[i] << " ";
else
os << (char)(x[i].val()+'A'-10) << " ";
}
else
os << ". ";
if((i+1)%(n*n) == 0)
os << std::endl << " ";
}
os << std::endl;
}
#ifdef GECODE_HAS_SET_VARS
private:
void same(Space& home, int nn, IntVarArgs a, IntVarArgs b) {
SetVar u(home, IntSet::empty, 1, nn);
rel(home, SOT_DUNION, a, u);
rel(home, SOT_DUNION, b, u);
}
IntVarArgs
block_col(Matrix<IntVarArray> m, int bc, int i, int j) {
return m.slice(bc*n+i, bc*n+i+1, j*n, (j+1)*n);
}
IntVarArgs
block_row(Matrix<IntVarArray> m, int br, int i, int j) {
return m.slice(j*n, (j+1)*n, br*n+i, br*n+i+1);
}
#endif
};
#ifdef GECODE_HAS_SET_VARS
class SudokuSet : virtual public Sudoku {
protected:
SetVarArray y;
public:
SudokuSet(const SizeOptions& opt)
: Sudoku(opt),
y(*this,n*n,IntSet::empty,1,n*n*n*n,
static_cast<unsigned int>(n*n),static_cast<unsigned int>(n*n)) {
const int nn = n*n;
Region r;
IntSet* row = r.alloc<IntSet>(nn);
IntSet* col = r.alloc<IntSet>(nn);
IntSet* block = r.alloc<IntSet>(nn);
// Set up the row and column set constants
int* dsc = r.alloc<int>(nn);
for (int i=0; i<nn; i++) {
row[i] = IntSet((i*nn)+1, (i+1)*nn);
for (int j=0; j<nn; j++) {
dsc[j] = (j*nn)+1+i;
}
col[i] = IntSet(dsc, nn);
}
// Set up the block set constants
int* dsb_arr = r.alloc<int>(nn);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
for (int ii=0; ii<n; ii++) {
for (int jj=0; jj<n; jj++) {
dsb_arr[ii*n+jj] = j*nn*n+i*n+jj*nn+ii+1;
}
}
block[i*n+j] = IntSet(dsb_arr, nn);
}
}
IntSet full(1, nn*nn);
// All x must be pairwise disjoint and partition the field indices
rel(*this, SOT_DUNION, y, SetVar(*this, full, full));
// The x must intersect in exactly one element with each
// row, column, and block
for (int i=0; i<nn; i++)
for (int j=0; j<nn; j++) {
SetVar inter_row(*this, IntSet::empty, full, 1U, 1U);
rel(*this, y[i], SOT_INTER, row[j], SRT_EQ, inter_row);
SetVar inter_col(*this, IntSet::empty, full, 1U, 1U);
rel(*this, y[i], SOT_INTER, col[j], SRT_EQ, inter_col);
SetVar inter_block(*this, IntSet::empty, full, 1U, 1U);
rel(*this, y[i], SOT_INTER, block[j], SRT_EQ, inter_block);
}
// Fill-in predefined fields
for (int i=0; i<nn; i++)
for (int j=0; j<nn; j++)
if (int idx = sudokuField(examples[opt.size()], nn, i, j))
dom(*this, y[idx-1], SRT_SUP, (i+1)+(j*nn) );
if (opt.branching() == BRANCH_NONE) {
branch(*this, y, SET_VAR_NONE(), SET_VAL_MIN_INC());
} else if (opt.branching() == BRANCH_SIZE) {
branch(*this, y, SET_VAR_SIZE_MIN(), SET_VAL_MIN_INC());
} else if (opt.branching() == BRANCH_SIZE_DEGREE) {
branch(*this, y, SET_VAR_DEGREE_SIZE_MAX(), SET_VAL_MIN_INC());
} else if (opt.branching() == BRANCH_SIZE_AFC) {
branch(*this, y, SET_VAR_AFC_SIZE_MAX(opt.decay()), SET_VAL_MIN_INC());
} else if (opt.branching() == BRANCH_AFC) {
branch(*this, y, SET_VAR_AFC_MAX(opt.decay()), SET_VAL_MIN_INC());
}
}
SudokuSet(SudokuSet& s) : Sudoku(s) {
y.update(*this, s.y);
}
virtual Space*
copy(void) {
return new SudokuSet(*this);
}
virtual void
print(std::ostream& os) const {
os << '\t';
for (int i = 0; i<n*n*n*n; i++) {
for (int j=0; j<n*n; j++) {
if (y[j].contains(i+1)) {
if (j+1<10)
os << j+1 << " ";
else
os << (char)(j+1+'A'-10) << " ";
break;
}
}
if((i+1)%(n*n) == 0)
os << std::endl << '\t';
}
os << std::endl;
}
};
class SudokuMixed : public SudokuInt, public SudokuSet {
public:
SudokuMixed(const SizeOptions& opt)
: Sudoku(opt), SudokuInt(opt), SudokuSet(opt) {
const int nn = n*n;
IntSet is0(0,0);
SetVar dummySet0(*this, is0, is0);
IntVar dummyInt0(*this, 0, 0);
SetVarArgs ys(nn+1);
ys[0] = dummySet0;
for (int i=0; i<nn; i++)
ys[i+1] = y[i];
IntVarArgs xs(nn*nn+1);
xs[0] = dummyInt0;
for (int i=0; i<nn*nn; i++)
xs[i+1] = x[i];
channel(*this, xs, ys);
IntArgs values(nn);
for (int i=0; i<nn; i++)
values[i] = i+1;
count(*this, x, IntSet(nn,nn), values, IPL_DOM);
}
SudokuMixed(SudokuMixed& s)
: Sudoku(s), SudokuInt(s), SudokuSet(s) {}
virtual Space*
copy(void) {
return new SudokuMixed(*this);
}
virtual void print(std::ostream& os) const { SudokuInt::print(os); }
};
#endif
int
main(int argc, char* argv[]) {
SizeOptions opt("Sudoku");
opt.size(0);
opt.ipl(IPL_DOM);
opt.solutions(1);
#ifdef GECODE_HAS_SET_VARS
opt.model(Sudoku::MODEL_INT);
opt.model(Sudoku::MODEL_INT, "int", "use integer constraints");
opt.model(Sudoku::MODEL_SET, "set", "use set constraints");
opt.model(Sudoku::MODEL_MIXED, "mixed",
"use both integer and set constraints");
opt.propagation(SudokuInt::PROP_NONE);
opt.propagation(SudokuInt::PROP_NONE, "none", "no additional constraints");
opt.propagation(SudokuInt::PROP_SAME, "same",
"additional \"same\" constraint for integer model");
#endif
opt.branching(Sudoku::BRANCH_SIZE_AFC);
opt.branching(Sudoku::BRANCH_NONE, "none", "none");
opt.branching(Sudoku::BRANCH_SIZE, "size", "min size");
opt.branching(Sudoku::BRANCH_SIZE_DEGREE, "sizedeg", "min size over degree");
opt.branching(Sudoku::BRANCH_SIZE_AFC, "sizeafc", "min size over afc");
opt.branching(Sudoku::BRANCH_AFC, "afc", "maximum afc");
opt.parse(argc,argv);
if (opt.size() >= n_examples) {
std::cerr << "Error: size must be between 0 and "
<< n_examples-1 << std::endl;
return 1;
}
#ifdef GECODE_HAS_SET_VARS
switch (opt.model()) {
case Sudoku::MODEL_INT:
Script::run<SudokuInt,DFS,SizeOptions>(opt);
break;
case Sudoku::MODEL_SET:
Script::run<SudokuSet,DFS,SizeOptions>(opt);
break;
case Sudoku::MODEL_MIXED:
Script::run<SudokuMixed,DFS,SizeOptions>(opt);
break;
}
#else
Script::run<SudokuInt,DFS,SizeOptions>(opt);
#endif
return 0;
}
// STATISTICS: example-any
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >::run
static void run(const Options &opt, Script *s=NULL)
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntSet::empty
static const IntSet empty
Empty set.
Definition int.hh:283
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::Matrix
Matrix-interface for arrays.
Definition minimodel.hh:2161
Gecode::Matrix::slice
Slice< A > slice(int fc, int tc, int fr, int tr) const
Access slice of the matrix.
Definition matrix.hpp:171
Gecode::Matrix::col
Slice< A > col(int c) const
Access column c.
Definition matrix.hpp:183
Gecode::Matrix::row
Slice< A > row(int r) const
Access row r.
Definition matrix.hpp:177
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::SetVarArgs
Passing set variables.
Definition set.hh:488
Gecode::SetVarArray
Set variable array
Definition set.hh:570
Gecode::SetVar
Set variables
Definition set.hh:127
Gecode::SizeOptions
Options for scripts with additional size parameter
Definition driver.hh:675
Gecode::Space
Computation spaces.
Definition core.hpp:1742
SudokuInt::copy
virtual Space * copy(void)
Perform copying during cloning.
Definition sudoku-advanced.cpp:188
SudokuInt::SudokuInt
SudokuInt(const SizeOptions &opt)
Constructor.
Definition sudoku-advanced.cpp:105
SudokuInt::print
virtual void print(std::ostream &os) const
Print solution.
Definition sudoku-advanced.cpp:194
SudokuInt::SudokuInt
SudokuInt(SudokuInt &s)
Constructor for cloning s.
Definition sudoku-advanced.cpp:182
SudokuInt::PROP_NONE
@ PROP_NONE
No additional constraints.
Definition sudoku-advanced.cpp:100
SudokuInt::PROP_SAME
@ PROP_SAME
Use "same" constraint with integer model.
Definition sudoku-advanced.cpp:101
SudokuInt::x
IntVarArray x
Values for the fields.
Definition sudoku-advanced.cpp:95
SudokuMixed::SudokuMixed
SudokuMixed(SudokuMixed &s)
Constructor for cloning s.
Definition sudoku-advanced.cpp:385
SudokuMixed::print
virtual void print(std::ostream &os) const
Print solution.
Definition sudoku-advanced.cpp:395
SudokuMixed::copy
virtual Space * copy(void)
Perform copying during cloning.
Definition sudoku-advanced.cpp:390
SudokuMixed::SudokuMixed
SudokuMixed(const SizeOptions &opt)
Constructor.
Definition sudoku-advanced.cpp:360
SudokuSet::y
SetVarArray y
The fields occupied by a certain number.
Definition sudoku-advanced.cpp:243
SudokuSet::copy
virtual Space * copy(void)
Perform copying during cloning.
Definition sudoku-advanced.cpp:325
SudokuSet::print
virtual void print(std::ostream &os) const
Print solution.
Definition sudoku-advanced.cpp:331
SudokuSet::SudokuSet
SudokuSet(SudokuSet &s)
Constructor for cloning s.
Definition sudoku-advanced.cpp:319
SudokuSet::SudokuSet
SudokuSet(const SizeOptions &opt)
Constructor.
Definition sudoku-advanced.cpp:246
Sudoku::main
int main(int argc, char *argv[])
Main-function.
Definition sudoku-advanced.cpp:405
Sudoku::MODEL_INT
@ MODEL_INT
Use integer constraints.
Definition sudoku-advanced.cpp:63
Sudoku::MODEL_SET
@ MODEL_SET
Use set constraints.
Definition sudoku-advanced.cpp:64
Sudoku::MODEL_MIXED
@ MODEL_MIXED
Use both integer and set constraints.
Definition sudoku-advanced.cpp:65
Sudoku::n_examples
const unsigned int n_examples
The number of instances.
Definition sudoku-instances.hh:1849
Sudoku::example_size
int example_size(const char *s)
The size of an instance.
Definition sudoku-instances.hh:1852
Sudoku::Sudoku
Sudoku(const SizeOptions &opt)
Constructor.
Definition sudoku-advanced.cpp:78
Sudoku::examples
const char * examples[]
The specifications.
Definition sudoku-instances.hh:54
Sudoku::sudokuField
int sudokuField(const char *s, int n, int i, int j)
Return value at position (i,j) in the example s of size n.
Definition sudoku-instances.hh:1860
Sudoku::n
const int n
The size of the problem.
Definition sudoku-advanced.cpp:58
Sudoku::BRANCH_NONE
@ BRANCH_NONE
Use lexicographic ordering.
Definition sudoku-advanced.cpp:70
Sudoku::BRANCH_SIZE_AFC
@ BRANCH_SIZE_AFC
Use minimum size over afc.
Definition sudoku-advanced.cpp:73
Sudoku::BRANCH_SIZE
@ BRANCH_SIZE
Use minimum size.
Definition sudoku-advanced.cpp:71
Sudoku::BRANCH_SIZE_DEGREE
@ BRANCH_SIZE_DEGREE
Use minimum size over degree.
Definition sudoku-advanced.cpp:72
Sudoku::BRANCH_AFC
@ BRANCH_AFC
Use maximum afc.
Definition sudoku-advanced.cpp:74
Sudoku::Sudoku
Sudoku(Sudoku &s)
Constructor for cloning s.
Definition sudoku-advanced.cpp:83
Test::Options::parse
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
driver.hh
int.hh
set.hh
Gecode::Script
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
Gecode::branch
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
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:926
Gecode::IPL_DOM
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:979
Gecode::SOT_DUNION
@ SOT_DUNION
Disjoint union.
Definition set.hh:662
Gecode::SOT_INTER
@ SOT_INTER
Intersection
Definition set.hh:663
Gecode::SRT_EQ
@ SRT_EQ
Equality ( ).
Definition set.hh:644
Gecode::SRT_SUP
@ SRT_SUP
Superset ( ).
Definition set.hh:647
minimodel.hh
Gecode
Gecode toplevel namespace
Gecode::INT_VAL_SPLIT_MIN
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition val.hpp:75
Gecode::count
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Gecode::INT_VAR_AFC_SIZE_MAX
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
Gecode::channel
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
Gecode::SET_VAR_NONE
SetVarBranch SET_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
Gecode::SET_VAR_DEGREE_SIZE_MAX
SetVarBranch SET_VAR_DEGREE_SIZE_MAX(BranchTbl tbl=nullptr)
Select variable with largest degree divided by domain size.
Definition var.hpp:221
Gecode::distinct
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
Gecode::INT_VAR_NONE
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
Gecode::dom
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition dom.cpp:40
Gecode::INT_VAR_AFC_MAX
IntVarBranch INT_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count with decay factor d.
Definition var.hpp:136
Gecode::SET_VAR_SIZE_MIN
SetVarBranch SET_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest unknown set.
Definition var.hpp:206
Gecode::same
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1937
Gecode::values
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
Gecode::SET_VAR_AFC_MAX
SetVarBranch SET_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count with decay factor d.
Definition var.hpp:136
Gecode::SET_VAL_MIN_INC
SetValBranch SET_VAL_MIN_INC(void)
Include smallest element.
Definition val.hpp:55
Gecode::SET_VAR_AFC_SIZE_MAX
SetVarBranch SET_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
Gecode::INT_VAR_DEGREE_SIZE_MAX
IntVarBranch INT_VAR_DEGREE_SIZE_MAX(BranchTbl tbl=nullptr)
Select variable with largest degree divided by domain size.
Definition var.hpp:221
Gecode::INT_VAR_SIZE_MIN
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
Definition var.hpp:206
sudoku-instances.hh