sudoku.cpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041
00042 #include <string>
00043 #include <cmath>
00044 #include <cctype>
00045
00046 using namespace Gecode;
00047
00048 #include <examples/sudoku-instances.hh>
00049
00055 class Sudoku : public Script {
00056 protected:
00058 const int n;
00060 IntVarArray x;
00061 public:
00062
00064 Sudoku(const SizeOptions& opt)
00065 : Script(opt),
00066 n(example_size(examples[opt.size()])),
00067 x(*this, n*n*n*n, 1, n*n) {
00068
00069 const int nn = n*n;
00070 Matrix<IntVarArray> m(x, nn, nn);
00071
00072
00073 for (int i=0; i<nn; i++) {
00074 distinct(*this, m.row(i), opt.ipl());
00075 distinct(*this, m.col(i), opt.ipl());
00076 }
00077
00078
00079 for (int i=0; i<nn; i+=n) {
00080 for (int j=0; j<nn; j+=n) {
00081 distinct(*this, m.slice(i, i+n, j, j+n), opt.ipl());
00082 }
00083 }
00084
00085
00086 for (int i=0; i<nn; i++)
00087 for (int j=0; j<nn; j++)
00088 if (int v = sudokuField(examples[opt.size()], nn, i, j))
00089 rel(*this, m(i,j), IRT_EQ, v );
00090
00091 branch(*this, x, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
00092 }
00093
00095 Sudoku(Sudoku& s) : Script(s), n(s.n) {
00096 x.update(*this, s.x);
00097 }
00098
00100 virtual Space*
00101 copy(void) {
00102 return new Sudoku(*this);
00103 }
00104
00106 virtual void
00107 print(std::ostream& os) const {
00108 os << " ";
00109 for (int i = 0; i<n*n*n*n; i++) {
00110 if (x[i].assigned()) {
00111 if (x[i].val()<10)
00112 os << x[i] << " ";
00113 else
00114 os << (char)(x[i].val()+'A'-10) << " ";
00115 }
00116 else
00117 os << ". ";
00118 if((i+1)%(n*n) == 0)
00119 os << std::endl << " ";
00120 }
00121 os << std::endl;
00122 }
00123
00124 };
00125
00129 int
00130 main(int argc, char* argv[]) {
00131 SizeOptions opt("Sudoku");
00132 opt.size(0);
00133 opt.ipl(IPL_DOM);
00134 opt.solutions(1);
00135 opt.parse(argc,argv);
00136 if (opt.size() >= n_examples) {
00137 std::cerr << "Error: size must be between 0 and "
00138 << n_examples-1 << std::endl;
00139 return 1;
00140 }
00141 Script::run<Sudoku,DFS,SizeOptions>(opt);
00142 return 0;
00143 }
00144
00145