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