word-square.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
00039
00040
00041
00042 #include <gecode/driver.hh>
00043
00044 #include <gecode/int.hh>
00045 #include <gecode/minimodel.hh>
00046
00047 #include "examples/scowl.hpp"
00048
00049 using namespace Gecode;
00050
00063 class WordSquare : public Script {
00064 protected:
00066 const int w_l;
00068 IntVarArray letters;
00069 public:
00071 enum {
00072 BRANCH_WORDS,
00073 BRANCH_LETTERS,
00074 };
00076 WordSquare(const SizeOptions& opt)
00077 : w_l(opt.size()), letters(*this, w_l*w_l) {
00078
00079
00080 Matrix<IntVarArray> ml(letters, w_l, w_l);
00081 for (int i=0; i<w_l; i++)
00082 for (int j=i; j<w_l; j++)
00083 ml(i,j) = ml(j,i) = IntVar(*this, 'a','z');
00084
00085
00086 const int n_w = dict.words(w_l);
00087
00088
00089 IntVarArgs words(w_l);
00090 for (int i=0; i<w_l; i++)
00091 words[i].init(*this,0,n_w-1);
00092
00093
00094 distinct(*this, words);
00095
00096
00097 for (int i=0; i<w_l; i++) {
00098
00099 IntSharedArray w2l(n_w);
00100 for (int n=n_w; n--; )
00101 w2l[n]=dict.word(w_l,n)[i];
00102 for (int j=0; j<w_l; j++)
00103 element(*this, w2l, words[j], ml(i,j));
00104 }
00105
00106
00107 rel(*this, words[0], IRT_LE, words[w_l-1]);
00108
00109 switch (opt.branching()) {
00110 case BRANCH_WORDS:
00111
00112 branch(*this, words, INT_VAR_SIZE_MIN, INT_VAL_SPLIT_MIN);
00113 break;
00114 case BRANCH_LETTERS:
00115
00116 branch(*this, letters, INT_VAR_SIZE_AFC_MIN, INT_VAL_MIN);
00117 break;
00118 }
00119 }
00121 WordSquare(bool share, WordSquare& s)
00122 : Script(share,s), w_l(s.w_l) {
00123 letters.update(*this, share, s.letters);
00124 }
00126 virtual Space*
00127 copy(bool share) {
00128 return new WordSquare(share,*this);
00129 }
00131 virtual void
00132 print(std::ostream& os) const {
00133 Matrix<IntVarArray> ml(letters, w_l, w_l);
00134 for (int i=0; i<w_l; i++) {
00135 os << "\t\t";
00136 for (int j=0; j<w_l; j++)
00137 if (ml(i,j).assigned()) {
00138 os << static_cast<char>(ml(i,j).val());
00139 } else {
00140 os << ".";
00141 }
00142 os << std::endl;
00143 }
00144 os << std::endl;
00145 }
00146 };
00147
00148
00152 int
00153 main(int argc, char* argv[]) {
00154 FileSizeOptions opt("WordSquare");
00155 opt.size(4);
00156 opt.branching(WordSquare::BRANCH_LETTERS);
00157 opt.branching(WordSquare::BRANCH_WORDS, "words");
00158 opt.branching(WordSquare::BRANCH_LETTERS, "letters");
00159 opt.parse(argc,argv);
00160 dict.init(opt.file());
00161 if (opt.size() > dict.len()) {
00162 std::cerr << "Error: size must be between 0 and "
00163 << dict.len() << std::endl;
00164 return 1;
00165 }
00166 Script::run<WordSquare,DFS,SizeOptions>(opt);
00167 return 0;
00168 }
00169
00170