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(*this, w_l, 0, n_w-1);
00090
00091
00092 distinct(*this, words);
00093
00094
00095 for (int i=0; i<w_l; i++) {
00096
00097 IntSharedArray w2l(n_w);
00098 for (int n=n_w; n--; )
00099 w2l[n]=dict.word(w_l,n)[i];
00100 for (int j=0; j<w_l; j++)
00101 element(*this, w2l, words[j], ml(i,j));
00102 }
00103
00104
00105 rel(*this, words[0], IRT_LE, words[w_l-1]);
00106
00107 switch (opt.branching()) {
00108 case BRANCH_WORDS:
00109
00110 branch(*this, words, INT_VAR_SIZE_MIN, INT_VAL_SPLIT_MIN);
00111 break;
00112 case BRANCH_LETTERS:
00113
00114 branch(*this, letters, INT_VAR_SIZE_AFC_MIN, INT_VAL_MIN);
00115 break;
00116 }
00117 }
00119 WordSquare(bool share, WordSquare& s)
00120 : Script(share,s), w_l(s.w_l) {
00121 letters.update(*this, share, s.letters);
00122 }
00124 virtual Space*
00125 copy(bool share) {
00126 return new WordSquare(share,*this);
00127 }
00129 virtual void
00130 print(std::ostream& os) const {
00131 Matrix<IntVarArray> ml(letters, w_l, w_l);
00132 for (int i=0; i<w_l; i++) {
00133 os << "\t\t";
00134 for (int j=0; j<w_l; j++)
00135 if (ml(i,j).assigned()) {
00136 os << static_cast<char>(ml(i,j).val());
00137 } else {
00138 os << ".";
00139 }
00140 os << std::endl;
00141 }
00142 os << std::endl;
00143 }
00144 };
00145
00146
00150 int
00151 main(int argc, char* argv[]) {
00152 FileSizeOptions opt("WordSquare");
00153 opt.size(6);
00154 opt.branching(WordSquare::BRANCH_LETTERS);
00155 opt.branching(WordSquare::BRANCH_WORDS, "words");
00156 opt.branching(WordSquare::BRANCH_LETTERS, "letters");
00157 opt.parse(argc,argv);
00158 dict.init(opt.file());
00159 if (opt.size() > static_cast<unsigned int>(dict.len())) {
00160 std::cerr << "Error: size must be between 0 and "
00161 << dict.len() << std::endl;
00162 return 1;
00163 }
00164 Script::run<WordSquare,DFS,SizeOptions>(opt);
00165 return 0;
00166 }
00167
00168