ortho-latin.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2010-04-23 16:53:08 +0200 (Fri, 23 Apr 2010) $ by $Author: tack $ 00011 * $Revision: 10801 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include <gecode/driver.hh> 00039 #include <gecode/int.hh> 00040 00041 using namespace Gecode; 00042 00048 class OrthoLatinSquare : public Script { 00049 protected: 00051 const int n; 00053 IntVarArray x1; 00055 IntVarArray x2; 00056 00057 public: 00059 IntVar& y1(int i, int j) { 00060 return x1[i*n+j]; 00061 } 00063 const IntVar& y1(int i, int j) const { 00064 return x1[i*n+j]; 00065 } 00067 IntVar& y2(int i, int j) { 00068 return x2[i*n+j]; 00069 } 00071 const IntVar& y2(int i, int j) const { 00072 return x2[i*n+j]; 00073 } 00074 00076 OrthoLatinSquare(const SizeOptions& opt) 00077 : n(opt.size()), 00078 x1(*this,n*n,1,n), x2(*this,n*n,1,n) { 00079 const int nn = n*n; 00080 IntVarArgs z(*this,nn,0,n*n-1); 00081 00082 distinct(*this, z, opt.icl()); 00083 // Connect 00084 { 00085 IntArgs mod(n*n); 00086 IntArgs div(n*n); 00087 for (int i=0; i<n; i++) 00088 for (int j=0; j<n; j++) { 00089 mod[i*n+j] = j+1; 00090 div[i*n+j] = i+1; 00091 } 00092 for (int i = nn; i--; ) { 00093 element(*this, div, z[i], x2[i]); 00094 element(*this, mod, z[i], x1[i]); 00095 } 00096 } 00097 00098 // Rows 00099 for (int i = n; i--; ) { 00100 IntVarArgs ry(n); 00101 for (int j = n; j--; ) 00102 ry[j] = y1(i,j); 00103 distinct(*this, ry, opt.icl()); 00104 for (int j = n; j--; ) 00105 ry[j] = y2(i,j); 00106 distinct(*this, ry, opt.icl()); 00107 } 00108 for (int j = n; j--; ) { 00109 IntVarArgs cy(n); 00110 for (int i = n; i--; ) 00111 cy[i] = y1(i,j); 00112 distinct(*this, cy, opt.icl()); 00113 for (int i = n; i--; ) 00114 cy[i] = y2(i,j); 00115 distinct(*this, cy, opt.icl()); 00116 } 00117 00118 for (int i = 1; i<n; i++) { 00119 IntVarArgs ry1(n); 00120 IntVarArgs ry2(n); 00121 for (int j = n; j--; ) { 00122 ry1[j] = y1(i-1,j); 00123 ry2[j] = y2(i,j); 00124 } 00125 rel(*this, ry1, IRT_GQ, ry2); 00126 } 00127 00128 branch(*this, z, INT_VAR_SIZE_MIN, INT_VAL_SPLIT_MIN); 00129 } 00130 00132 OrthoLatinSquare(bool share, OrthoLatinSquare& s) 00133 : Script(share,s), n(s.n) { 00134 x1.update(*this, share, s.x1); 00135 x2.update(*this, share, s.x2); 00136 } 00137 00139 virtual Space* 00140 copy(bool share) { 00141 return new OrthoLatinSquare(share,*this); 00142 } 00144 virtual void 00145 print(std::ostream& os) const { 00146 for (int i = 0; i<n; i++) { 00147 os << "\t"; 00148 for (int j = 0; j<n; j++) { 00149 os.width(2); 00150 os << y1(i,j) << " "; 00151 } 00152 os << std::endl; 00153 } 00154 os << std::endl; 00155 for (int i = 0; i<n; i++) { 00156 os << "\t"; 00157 for (int j = 0; j<n; j++) { 00158 os.width(2); 00159 os << y2(i,j) << " "; 00160 } 00161 os << std::endl; 00162 } 00163 os << std::endl; 00164 } 00165 00166 }; 00167 00172 int 00173 main(int argc, char* argv[]) { 00174 SizeOptions opt("OrthoLatinSquare"); 00175 opt.size(7); 00176 opt.icl(ICL_DOM); 00177 opt.parse(argc,argv); 00178 Script::run<OrthoLatinSquare,DFS,SizeOptions>(opt); 00179 return 0; 00180 } 00181 00182 // STATISTICS: example-any 00183