Generated on Tue May 22 09:39:40 2018 for Gecode by doxygen 1.6.3

word-square.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Håkan Kjellerstrand <hakank@bonetmail.com>
00005  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00006  *     Christian Schulte <schulte@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Håkan Kjellerstrand, 2009
00010  *     Mikael Lagerkvist, 2009
00011  *     Christian Schulte, 2009
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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     // Initialize letters
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     // Number of words with that length
00082     const int n_w = dict.words(w_l);
00083 
00084     // Initialize word array
00085     IntVarArgs words(*this, w_l, 0, n_w-1);
00086 
00087     // All words must be different
00088     distinct(*this, words);
00089 
00090     // Link words with letters
00091     for (int i=0; i<w_l; i++) {
00092       // Map each word to i-th letter in that word
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     // Symmetry breaking: the last word must be later in the wordlist
00101     rel(*this, words[0], IRT_LE, words[w_l-1]);
00102 
00103     switch (opt.branching()) {
00104     case BRANCH_WORDS:
00105       // Branch by assigning words
00106       branch(*this, words, INT_VAR_SIZE_MIN(), INT_VAL_SPLIT_MIN());
00107       break;
00108     case BRANCH_LETTERS:
00109       // Branch by assigning letters
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 // STATISTICS: example-any