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: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00015 * $Revision: 11473 $ 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 = dict.words(w_l); 00087 00088 // Initialize word array 00089 IntVarArgs words(*this, w_l, 0, n_w-1); 00090 00091 // All words must be different 00092 distinct(*this, words); 00093 00094 // Link words with letters 00095 for (int i=0; i<w_l; i++) { 00096 // Map each word to i-th letter in that word 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 // Symmetry breaking: the last word must be later in the wordlist 00105 rel(*this, words[0], IRT_LE, words[w_l-1]); 00106 00107 switch (opt.branching()) { 00108 case BRANCH_WORDS: 00109 // Branch by assigning words 00110 branch(*this, words, INT_VAR_SIZE_MIN, INT_VAL_SPLIT_MIN); 00111 break; 00112 case BRANCH_LETTERS: 00113 // Branch by assigning letters 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 // STATISTICS: example-any