this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2011
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/driver.hh>
35#include <gecode/int.hh>
36#include <gecode/minimodel.hh>
37
38using namespace Gecode;
39
40/**
41 * \brief %Options for Schur's Lemma
42 *
43 */
44class SchurOptions : public Options {
45public:
46 int c, n; ///< Parameters to be given on command line
47 /// Initialize options for example with name \a s
48 SchurOptions(const char* s, int c0, int n0)
49 : Options(s), c(c0), n(n0) {}
50 /// Parse options from arguments \a argv (number is \a argc)
51 void parse(int& argc, char* argv[]) {
52 Options::parse(argc,argv);
53 if (argc < 3)
54 return;
55 c = atoi(argv[1]);
56 n = atoi(argv[2]);
57 }
58 /// Print help message
59 virtual void help(void) {
60 Options::help();
61 std::cerr << "\t(unsigned int) default: " << c << std::endl
62 << "\t\tparameter c (number of boxes)" << std::endl
63 << "\t(unsigned int) default: " << n << std::endl
64 << "\t\tparameter n (number of balls)" << std::endl;
65 }
66};
67
68
69/**
70 * \brief %Example: Schur's lemma
71 *
72 * Put \f$n\f$ balls labeled \f${1,\ldots,n}\f$ into \f$c\f$ boxes such
73 * that for any triple of balls \f$\langle x, y, z\rangle\f$ with
74 * \f$x+y = z\f$, not all are in the same box.
75 *
76 * This problem has a solution for \f$c=3\f$ if \f$n < 14\f$.
77 *
78 * See also problem 15 at http://www.csplib.org/.
79 *
80 * \ingroup Example
81 *
82 */
83class Schur : public Script {
84protected:
85 /// Array of box per ball
86 IntVarArray box;
87public:
88 /// Actual model
89 Schur(const SchurOptions& opt)
90 : Script(opt), box(*this,opt.n,1,opt.c) {
91 int n = opt.n;
92
93 // Iterate over balls and find triples
94 for (int i=1; i<=n; i++)
95 for (int j=1; i+j<=n; j++)
96 rel(*this, {box[i-1],box[j-1],box[i+j-1]}, IRT_NQ);
97
98 // Break value symmetries
99 precede(*this, box, IntArgs::create(opt.c, 1));
100
101 branch(*this, box, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
102 }
103 /// Print solution
104 virtual void
105 print(std::ostream& os) const {
106 os << "\t" << box << std::endl;
107 }
108
109 /// Constructor for cloning \a s
110 Schur(Schur& s) : Script(s) {
111 box.update(*this, s.box);
112 }
113 /// Copy during cloning
114 virtual Space*
115 copy(void) {
116 return new Schur(*this);
117 }
118};
119
120/** \brief Main-function
121 * \relates Schur
122 */
123int
124main(int argc, char* argv[]) {
125 SchurOptions opt("Schur's Lemma",3,13);
126 opt.parse(argc,argv);
127 Script::run<Schur,DFS,SchurOptions>(opt);
128 return 0;
129}
130
131// STATISTICS: example-any
132