word-square.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Håkan Kjellerstrand <hakank@bonetmail.com>
* Mikael Lagerkvist <lagerkvist@gecode.org>
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Håkan Kjellerstrand, 2009
* Mikael Lagerkvist, 2009
* Christian Schulte, 2009
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
#include "examples/scowl.hpp"
using namespace Gecode;
class WordSquare : public Script {
protected:
const int w_l;
IntVarArray letters;
public:
enum {
BRANCH_WORDS,
BRANCH_LETTERS,
};
WordSquare(const SizeOptions& opt)
: Script(opt), w_l(opt.size()), letters(*this, w_l*w_l) {
// Initialize letters
Matrix<IntVarArray> ml(letters, w_l, w_l);
for (int i=0; i<w_l; i++)
for (int j=i; j<w_l; j++)
ml(i,j) = ml(j,i) = IntVar(*this, 'a','z');
// Number of words with that length
const int n_w = dict.words(w_l);
// Initialize word array
IntVarArgs words(*this, w_l, 0, n_w-1);
// All words must be different
distinct(*this, words);
// Link words with letters
for (int i=0; i<w_l; i++) {
// Map each word to i-th letter in that word
IntSharedArray w2l(n_w);
for (int n=0; n<n_w; n++)
w2l[n]=dict.word(w_l,n)[i];
for (int j=0; j<w_l; j++)
element(*this, w2l, words[j], ml(i,j));
}
// Symmetry breaking: the last word must be later in the wordlist
rel(*this, words[0], IRT_LE, words[w_l-1]);
switch (opt.branching()) {
case BRANCH_WORDS:
// Branch by assigning words
branch(*this, words, INT_VAR_SIZE_MIN(), INT_VAL_SPLIT_MIN());
break;
case BRANCH_LETTERS:
// Branch by assigning letters
branch(*this, letters, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
break;
}
}
WordSquare(WordSquare& s)
: Script(s), w_l(s.w_l) {
letters.update(*this, s.letters);
}
virtual Space*
copy(void) {
return new WordSquare(*this);
}
virtual void
print(std::ostream& os) const {
Matrix<IntVarArray> ml(letters, w_l, w_l);
for (int i=0; i<w_l; i++) {
os << "\t\t";
for (int j=0; j<w_l; j++)
if (ml(i,j).assigned()) {
os << static_cast<char>(ml(i,j).val());
} else {
os << ".";
}
os << std::endl;
}
os << std::endl;
}
};
int
main(int argc, char* argv[]) {
FileSizeOptions opt("WordSquare");
opt.size(6);
opt.branching(WordSquare::BRANCH_LETTERS);
opt.branching(WordSquare::BRANCH_WORDS, "words");
opt.branching(WordSquare::BRANCH_LETTERS, "letters");
opt.parse(argc,argv);
dict.init(opt.file());
if (opt.size() > static_cast<unsigned int>(dict.len())) {
std::cerr << "Error: size must be between 0 and "
<< dict.len() << std::endl;
return 1;
}
Script::run<WordSquare,DFS,SizeOptions>(opt);
return 0;
}
// STATISTICS: example-any
FileSizeOptions
Parse an additional file option.
Definition scowl.hpp:37
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >::run
static void run(const Options &opt, Script *s=NULL)
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::Matrix
Matrix-interface for arrays.
Definition minimodel.hh:2161
Gecode::SizeOptions
Options for scripts with additional size parameter
Definition driver.hh:675
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Test::Options::parse
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
WordSquare::letters
IntVarArray letters
The array of letters.
Definition word-square.cpp:64
WordSquare::main
int main(int argc, char *argv[])
Main-function.
Definition word-square.cpp:147
WordSquare::print
virtual void print(std::ostream &os) const
Print solution.
Definition word-square.cpp:126
WordSquare::WordSquare
WordSquare(WordSquare &s)
Constructor for cloning s.
Definition word-square.cpp:115
WordSquare::BRANCH_LETTERS
@ BRANCH_LETTERS
Branch on letter variables.
Definition word-square.cpp:69
WordSquare::BRANCH_WORDS
@ BRANCH_WORDS
Branch on word variables.
Definition word-square.cpp:68
WordSquare::copy
virtual Space * copy(void)
Copy during cloning.
Definition word-square.cpp:121
WordSquare::WordSquare
WordSquare(const SizeOptions &opt)
Actual model.
Definition word-square.cpp:72
WordSquare::w_l
const int w_l
Length of words.
Definition word-square.cpp:62
driver.hh
int.hh
Gecode::Script
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
Gecode::branch
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::IRT_LE
@ IRT_LE
Less ( ).
Definition int.hh:929
minimodel.hh
Gecode
Gecode toplevel namespace
Gecode::INT_VAL_SPLIT_MIN
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition val.hpp:75
Gecode::INT_VAR_AFC_SIZE_MAX
IntVarBranch INT_VAR_AFC_SIZE_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count divided by domain size with decay factor d.
Definition var.hpp:236
Gecode::IntSharedArray
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
Definition int.hh:1477
Gecode::distinct
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
Gecode::element
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
Definition element.cpp:39
Gecode::INT_VAL_MIN
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
Gecode::INT_VAR_SIZE_MIN
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
Definition var.hpp:206
scowl.hpp
dict
Dictionary dict
The dictionary to be used.
Definition scowl.hpp:95