00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
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 : Script(opt),
00078 n(opt.size()),
00079 x1(*this,n*n,1,n), x2(*this,n*n,1,n) {
00080 const int nn = n*n;
00081 IntVarArgs z(*this,nn,0,n*n-1);
00082
00083 distinct(*this, z, opt.ipl());
00084
00085 {
00086 IntArgs mod(n*n);
00087 IntArgs div(n*n);
00088 for (int i=0; i<n; i++)
00089 for (int j=0; j<n; j++) {
00090 mod[i*n+j] = j+1;
00091 div[i*n+j] = i+1;
00092 }
00093 for (int i = nn; i--; ) {
00094 element(*this, div, z[i], x2[i]);
00095 element(*this, mod, z[i], x1[i]);
00096 }
00097 }
00098
00099
00100 for (int i = n; i--; ) {
00101 IntVarArgs ry(n);
00102 for (int j = n; j--; )
00103 ry[j] = y1(i,j);
00104 distinct(*this, ry, opt.ipl());
00105 for (int j = n; j--; )
00106 ry[j] = y2(i,j);
00107 distinct(*this, ry, opt.ipl());
00108 }
00109 for (int j = n; j--; ) {
00110 IntVarArgs cy(n);
00111 for (int i = n; i--; )
00112 cy[i] = y1(i,j);
00113 distinct(*this, cy, opt.ipl());
00114 for (int i = n; i--; )
00115 cy[i] = y2(i,j);
00116 distinct(*this, cy, opt.ipl());
00117 }
00118
00119 for (int i = 1; i<n; i++) {
00120 IntVarArgs ry1(n);
00121 IntVarArgs ry2(n);
00122 for (int j = n; j--; ) {
00123 ry1[j] = y1(i-1,j);
00124 ry2[j] = y2(i,j);
00125 }
00126 rel(*this, ry1, IRT_GQ, ry2);
00127 }
00128
00129 branch(*this, z, INT_VAR_SIZE_MIN(), INT_VAL_SPLIT_MIN());
00130 }
00131
00133 OrthoLatinSquare(bool share, OrthoLatinSquare& s)
00134 : Script(share,s), n(s.n) {
00135 x1.update(*this, share, s.x1);
00136 x2.update(*this, share, s.x2);
00137 }
00138
00140 virtual Space*
00141 copy(bool share) {
00142 return new OrthoLatinSquare(share,*this);
00143 }
00145 virtual void
00146 print(std::ostream& os) const {
00147 for (int i = 0; i<n; i++) {
00148 os << "\t";
00149 for (int j = 0; j<n; j++) {
00150 os.width(2);
00151 os << y1(i,j) << " ";
00152 }
00153 os << std::endl;
00154 }
00155 os << std::endl;
00156 for (int i = 0; i<n; i++) {
00157 os << "\t";
00158 for (int j = 0; j<n; j++) {
00159 os.width(2);
00160 os << y2(i,j) << " ";
00161 }
00162 os << std::endl;
00163 }
00164 os << std::endl;
00165 }
00166
00167 };
00168
00173 int
00174 main(int argc, char* argv[]) {
00175 SizeOptions opt("OrthoLatinSquare");
00176 opt.size(7);
00177 opt.ipl(IPL_DOM);
00178 opt.parse(argc,argv);
00179 Script::run<OrthoLatinSquare,DFS,SizeOptions>(opt);
00180 return 0;
00181 }
00182
00183
00184