this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Håkan Kjellerstrand <hakank@bonetmail.com>
5 * Mikael Lagerkvist <lagerkvist@gecode.org>
6 * Christian Schulte <schulte@gecode.org>
7 *
8 * Copyright:
9 * Håkan Kjellerstrand, 2009
10 * Mikael Lagerkvist, 2009
11 * Christian Schulte, 2009
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#include <gecode/driver.hh>
39
40#include <gecode/int.hh>
41#include <gecode/minimodel.hh>
42
43#include "examples/scowl.hpp"
44
45using namespace Gecode;
46
47/**
48 * \brief %Example: Word-square puzzle
49 *
50 * From http://en.wikipedia.org/wiki/Word_square:
51 * A word square is a special case of acrostic. It consists of a set of words,
52 * all having the same number of letters as the total number of words (the
53 * "order" of the square); when the words are written out in a square grid
54 * horizontally, the same set of words can be read vertically.
55 *
56 * \ingroup Example
57 *
58 */
59class WordSquare : public Script {
60protected:
61 /// Length of words
62 const int w_l;
63 /// The array of letters
64 IntVarArray letters;
65public:
66 /// Branching variants
67 enum {
68 BRANCH_WORDS, ///< Branch on word variables
69 BRANCH_LETTERS, ///< Branch on letter variables
70 };
71 /// Actual model
72 WordSquare(const SizeOptions& opt)
73 : Script(opt), w_l(opt.size()), letters(*this, w_l*w_l) {
74
75 // Initialize letters
76 Matrix<IntVarArray> ml(letters, w_l, w_l);
77 for (int i=0; i<w_l; i++)
78 for (int j=i; j<w_l; j++)
79 ml(i,j) = ml(j,i) = IntVar(*this, 'a','z');
80
81 // Number of words with that length
82 const int n_w = dict.words(w_l);
83
84 // Initialize word array
85 IntVarArgs words(*this, w_l, 0, n_w-1);
86
87 // All words must be different
88 distinct(*this, words);
89
90 // Link words with letters
91 for (int i=0; i<w_l; i++) {
92 // Map each word to i-th letter in that word
93 IntSharedArray w2l(n_w);
94 for (int n=0; n<n_w; n++)
95 w2l[n]=dict.word(w_l,n)[i];
96 for (int j=0; j<w_l; j++)
97 element(*this, w2l, words[j], ml(i,j));
98 }
99
100 // Symmetry breaking: the last word must be later in the wordlist
101 rel(*this, words[0], IRT_LE, words[w_l-1]);
102
103 switch (opt.branching()) {
104 case BRANCH_WORDS:
105 // Branch by assigning words
106 branch(*this, words, INT_VAR_SIZE_MIN(), INT_VAL_SPLIT_MIN());
107 break;
108 case BRANCH_LETTERS:
109 // Branch by assigning letters
110 branch(*this, letters, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
111 break;
112 }
113 }
114 /// Constructor for cloning \a s
115 WordSquare(WordSquare& s)
116 : Script(s), w_l(s.w_l) {
117 letters.update(*this, s.letters);
118 }
119 /// Copy during cloning
120 virtual Space*
121 copy(void) {
122 return new WordSquare(*this);
123 }
124 /// Print solution
125 virtual void
126 print(std::ostream& os) const {
127 Matrix<IntVarArray> ml(letters, w_l, w_l);
128 for (int i=0; i<w_l; i++) {
129 os << "\t\t";
130 for (int j=0; j<w_l; j++)
131 if (ml(i,j).assigned()) {
132 os << static_cast<char>(ml(i,j).val());
133 } else {
134 os << ".";
135 }
136 os << std::endl;
137 }
138 os << std::endl;
139 }
140};
141
142
143/** \brief Main-function
144 * \relates WordSquare
145 */
146int
147main(int argc, char* argv[]) {
148 FileSizeOptions opt("WordSquare");
149 opt.size(6);
150 opt.branching(WordSquare::BRANCH_LETTERS);
151 opt.branching(WordSquare::BRANCH_WORDS, "words");
152 opt.branching(WordSquare::BRANCH_LETTERS, "letters");
153 opt.parse(argc,argv);
154 dict.init(opt.file());
155 if (opt.size() > static_cast<unsigned int>(dict.len())) {
156 std::cerr << "Error: size must be between 0 and "
157 << dict.len() << std::endl;
158 return 1;
159 }
160 Script::run<WordSquare,DFS,SizeOptions>(opt);
161 return 0;
162}
163
164// STATISTICS: example-any