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 #include <gecode/driver.hh>
00035 #include <gecode/int.hh>
00036
00037 using namespace Gecode;
00038
00044 class OrthoLatinSquare : public Script {
00045 protected:
00047 const int n;
00049 IntVarArray x1;
00051 IntVarArray x2;
00052
00053 public:
00055 IntVar& y1(int i, int j) {
00056 return x1[i*n+j];
00057 }
00059 const IntVar& y1(int i, int j) const {
00060 return x1[i*n+j];
00061 }
00063 IntVar& y2(int i, int j) {
00064 return x2[i*n+j];
00065 }
00067 const IntVar& y2(int i, int j) const {
00068 return x2[i*n+j];
00069 }
00070
00072 OrthoLatinSquare(const SizeOptions& opt)
00073 : Script(opt),
00074 n(opt.size()),
00075 x1(*this,n*n,1,n), x2(*this,n*n,1,n) {
00076 const int nn = n*n;
00077 IntVarArgs z(*this,nn,0,n*n-1);
00078
00079 distinct(*this, z, opt.ipl());
00080
00081 {
00082 IntArgs mod(n*n);
00083 IntArgs div(n*n);
00084 for (int i=0; i<n; i++)
00085 for (int j=0; j<n; j++) {
00086 mod[i*n+j] = j+1;
00087 div[i*n+j] = i+1;
00088 }
00089 for (int i = nn; i--; ) {
00090 element(*this, div, z[i], x2[i]);
00091 element(*this, mod, z[i], x1[i]);
00092 }
00093 }
00094
00095
00096 for (int i = n; i--; ) {
00097 IntVarArgs ry(n);
00098 for (int j = n; j--; )
00099 ry[j] = y1(i,j);
00100 distinct(*this, ry, opt.ipl());
00101 for (int j = n; j--; )
00102 ry[j] = y2(i,j);
00103 distinct(*this, ry, opt.ipl());
00104 }
00105 for (int j = n; j--; ) {
00106 IntVarArgs cy(n);
00107 for (int i = n; i--; )
00108 cy[i] = y1(i,j);
00109 distinct(*this, cy, opt.ipl());
00110 for (int i = n; i--; )
00111 cy[i] = y2(i,j);
00112 distinct(*this, cy, opt.ipl());
00113 }
00114
00115 for (int i = 1; i<n; i++) {
00116 IntVarArgs ry1(n);
00117 IntVarArgs ry2(n);
00118 for (int j = n; j--; ) {
00119 ry1[j] = y1(i-1,j);
00120 ry2[j] = y2(i,j);
00121 }
00122 rel(*this, ry1, IRT_GQ, ry2);
00123 }
00124
00125 branch(*this, z, INT_VAR_SIZE_MIN(), INT_VAL_SPLIT_MIN());
00126 }
00127
00129 OrthoLatinSquare(OrthoLatinSquare& s)
00130 : Script(s), n(s.n) {
00131 x1.update(*this, s.x1);
00132 x2.update(*this, s.x2);
00133 }
00134
00136 virtual Space*
00137 copy(void) {
00138 return new OrthoLatinSquare(*this);
00139 }
00141 virtual void
00142 print(std::ostream& os) const {
00143 for (int i = 0; i<n; i++) {
00144 os << "\t";
00145 for (int j = 0; j<n; j++) {
00146 os.width(2);
00147 os << y1(i,j) << " ";
00148 }
00149 os << std::endl;
00150 }
00151 os << std::endl;
00152 for (int i = 0; i<n; i++) {
00153 os << "\t";
00154 for (int j = 0; j<n; j++) {
00155 os.width(2);
00156 os << y2(i,j) << " ";
00157 }
00158 os << std::endl;
00159 }
00160 os << std::endl;
00161 }
00162
00163 };
00164
00169 int
00170 main(int argc, char* argv[]) {
00171 SizeOptions opt("OrthoLatinSquare");
00172 opt.size(7);
00173 opt.ipl(IPL_DOM);
00174 opt.parse(argc,argv);
00175 Script::run<OrthoLatinSquare,DFS,SizeOptions>(opt);
00176 return 0;
00177 }
00178
00179
00180