OKlibrary  0.2.1.6
Schur_BHR.cpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 27.8.2012 (Swansea)
00002 /* Copyright 2012 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00057 #include <cstdio>
00058 #include <algorithm>
00059 #include <iostream>
00060 #include <cassert>
00061 #include <string>
00062 
00063 namespace {
00064 
00065   const std::string program = "Schur_BHR";
00066   const std::string version = "0.1.8";
00067 
00068 #ifndef COLS
00069 
00070 # define COLS 3
00071 #endif
00072 #ifndef UPB // upper bound for n for expected solutions
00073 
00074 # define UPB 24
00075 #endif
00076 #ifndef LOWB // lower bound for n on enumerated solutions
00077 
00078 # define LOWB 23
00079 #endif
00080 
00081   const unsigned int cols = COLS;
00082   const unsigned int upb = UPB+1;
00083   const unsigned int lowb = LOWB-1;
00084 
00085   long unsigned int count = 0;
00086 
00087   short unsigned int Base[cols][upb+1] = {};
00088   short unsigned int wsol[upb];
00089   unsigned int nums[upb+1][upb+1];
00090   unsigned int wmax = 0, max = lowb;
00091 
00092   inline void updatesol() {
00093     // there seems to be an error in the original code: "max" is redefined
00094     static unsigned int lprint = 0;
00095     max = wmax;
00096     assert(max < upb);
00097     if (max > lowb and max >= lprint) {
00098       for (unsigned int i = 1; i <= max; ++i) std::printf("%u", wsol[i]+1);
00099       std::printf(" %u %lu\n", wmax, ++count); // also here apparently errors in original
00100       lprint = max;
00101     }
00102     std::cout.flush();
00103   }
00104 
00105   inline bool excludedp(const unsigned int n) {
00106     assert(n <= upb);
00107     bool res = true;
00108     // apparently error in original:
00109     for (unsigned int i = 0; i < cols; ++i) res &= Base[i][n];
00110     return res;
00111   }
00112 
00113   inline unsigned int add_col(const unsigned int col) {
00114     assert(wmax + 1 < upb);
00115     wsol[++wmax] = col;
00116     if (wmax >= max) updatesol();
00117     unsigned int ex = 0;
00118     {unsigned int j = 1;
00119      assert(wmax <= upb);
00120      for (unsigned int i = 1; i < std::min(wmax, upb-wmax); ++i) {
00121        const unsigned int sum = wmax + i;
00122        if (wsol[i] == col) {
00123          nums[wmax][j++] = sum;
00124          ++Base[col][sum];
00125          if ((sum < std::max(lowb, max)) and excludedp(sum)) ++ex;
00126        }
00127      }
00128     }
00129     return ex;
00130   }
00131 
00132   inline void del_col() {
00133     assert(wmax < upb);
00134     const unsigned short int col = wsol[wmax];
00135     {unsigned int i = 1;
00136      while (nums[wmax][i]) {
00137        assert(Base[col][nums[wmax][i]] >= 1);
00138        --Base[col][nums[wmax][i]];
00139        nums[wmax][i++] = 0;
00140        assert(i <= upb or nums[wmax][i] == 0);
00141      }
00142     }
00143     --wmax;
00144   }
00145 
00146   inline bool colp(const unsigned int x) {
00147     assert(x < cols);
00148     assert(wmax < upb);
00149     return not Base[x][wmax+1];
00150   }
00151 
00152   inline void brute_force(const unsigned int b) {
00153     for (unsigned int i = 0; i < std::min(cols,b+1); ++i)
00154       if (colp(i)) {
00155         if (not add_col(i)) brute_force(std::max(i+1, b));
00156         del_col();
00157       }
00158   }
00159   
00160 }
00161 
00162 int main() {
00163   brute_force(0);
00164 }