fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. #define Nmax 8
  6. int N;
  7. int ts[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
  8.  
  9. struct plansza {bool P[Nmax][Nmax];
  10.   bool operator==(const plansza &P);
  11.   bool equals(plansza P);
  12.   plansza  symH();
  13.   plansza  rot90();
  14.   plansza  rot180();
  15.   }P0;
  16. vector<plansza> tp;
  17. bool W[Nmax];
  18. plansza P;
  19.  
  20. void show(const plansza &P);
  21. bool ss(int w, int k);
  22.  
  23. void uws(int w, int k) {
  24.   if (W[w]) return;
  25.   if (!ss(w,k)) return;
  26.   W[w]=true;
  27.   P.P[w][k]=true;
  28.   if (k==N-1) {
  29.     bool same=false;
  30.     for (int i=0;!same && i<tp.size();++i)  same=tp[i].equals(P);
  31.     if (!same) 
  32.       tp.push_back(P); 
  33.     }
  34.   else
  35.     for (int i=0;i<N;++i) uws(i,k+1);
  36.   W[w]=false;
  37.   P.P[w][k]=false;
  38.   }
  39.  
  40. int main() {
  41. for (N=1;N<=Nmax;++N) {
  42.   tp.clear();
  43.   P=P0;
  44.   for (int i=0;i<N;++i)    
  45.     uws(i,0);
  46.   printf("%d\t%d\n",N,tp.size());
  47.   //for(int i=0;i<tp.size();++i) {printf("%d\n",i);show(tp[i]);}
  48.   }
  49. return 0;
  50. }
  51.  
  52. void show(const plansza &P) {
  53.   for (int i=0;i<N;++i) { 
  54.     for (int j=0;j<N;++j)
  55.       printf("%c",P.P[i][j]?'X':'o');
  56.     printf("\n");
  57.     }
  58.   printf("\n");
  59.   }
  60.  
  61. bool ss(int w, int k) {
  62.   bool ok=true;    
  63.   for (int i=0;ok && i<8;++i) {
  64.     int x=w+ts[i][0];    if (x<0 || x>N-1) continue;
  65.     int y=k+ts[i][1];    if (y<0 || y>N-1) continue;
  66.     ok=!P.P[x][y];
  67.     }
  68.   return ok;    
  69.   }
  70.  
  71. bool plansza::operator==(const plansza &Q) {
  72.   bool ok=true;    
  73.   for (int i=0;ok && i<N;++i)
  74.     for (int j=0;ok &&j<N;++j)
  75.       ok=P[i][j]==Q.P[i][j];
  76.   return ok;    
  77.   }
  78.  
  79. plansza plansza::symH() {
  80.   plansza P=*this;
  81.   for (int i=0;i<N;++i)
  82.     for (int j=0;j<(N+1)/2;++j) {
  83.       bool p=P.P[i][j];
  84.       P.P[i][j]=P.P[i][N-1-j];
  85.       P.P[i][N-1-j]=p;
  86.       }
  87.   return P;      
  88.   };
  89.  
  90. plansza plansza::rot90() {
  91.   plansza Q;
  92.   for (int i=0;i<N;++i)
  93.     for (int j=0;j<N;++j)
  94.        Q.P[j][N-1-i]=P[i][j];
  95.   return Q;
  96.   }
  97.  
  98. plansza plansza::rot180() {
  99.   plansza Q;
  100.   for (int i=0;i<N;++i)
  101.     for (int j=0;j<N;++j)
  102.        Q.P[N-1-i][N-1-j]=P[i][j];
  103.   return Q;
  104.   }
  105.  
  106. bool plansza::equals(plansza P) {
  107.     if (*this==P.rot90())  return true;
  108.     if (*this==P.rot180())  return true;
  109.     if (P==this->rot90())  return true;
  110.     if (*this==P.symH())  return true;
  111.     P=P.symH();
  112.     if (*this==P.rot90())  return true;
  113.     if (*this==P.rot180())  return true;
  114.     if (P==this->rot90())  return true;
  115.     return false;
  116.     }
  117.  
Success #stdin #stdout 0.54s 2816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1	1
2	1
3	1
4	3
5	6
6	21
7	75
8	415
https://ideone.com/6bKsz
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!