Generated on Mon Nov 30 23:53:18 2009 for Gecode by doxygen 1.6.1

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  *  Last modified:
00014  *     $Date: 2009-11-04 12:22:16 +0100 (Wed, 04 Nov 2009) $ by $Author: schulte $
00015  *     $Revision: 10040 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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     // Initialize letters
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     // Number of words with that length
00086     const int n_w = n_words[w_l];
00087 
00088     // Initialize word array
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     // All words must be different
00094     distinct(*this, words);
00095 
00096     // Link words with letters
00097     for (int i=0; i<w_l; i++) {
00098       // Map each word to i-th letter in that word
00099       IntSharedArray w2l(n_w);
00100       for (int n=n_w; n--; )
00101         w2l[n]=dict[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     // Symmetry breaking: the last word must be later in the wordlist
00107     rel(*this, words[0], IRT_LE, words[w_l-1]);
00108 
00109     switch (opt.branching()) {
00110     case BRANCH_WORDS:
00111       // Branch by assigning words
00112       branch(*this, words, INT_VAR_SIZE_MIN, INT_VAL_SPLIT_MIN);
00113       break;
00114     case BRANCH_LETTERS:
00115       // Branch by assigning letters
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   SizeOptions 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   if (opt.size() > max_word_len) {
00161     std::cerr << "Error: size must be between 0 and "
00162               << max_word_len << std::endl;
00163     return 1;
00164   }
00165   Script::run<WordSquare,DFS,SizeOptions>(opt);
00166   return 0;
00167 }
00168 
00169 // STATISTICS: example-any