#include #include #include /* This very simple C program computes a(1),a(2),a(3) and a(4) for sequences A227299, A227005, A227257, A227301. Please do not take this as an example of good programming style. It is not. On my CPU (i7-3930k) a(4), (i.e. N=8) takes about 30 minutes. I have not optimized it further since it was not necessary. The largest part of the time is spent in cycles generation, while classifying the cycles takes a negligible time. The program cannot be used for larger N since the time explodes. I compiled it with gcc using the switch -std=c99 or -std=gnu99 to allow things like for (int i=0; i<3; i++) where var i is declared in for. I used all the possible optimizing switches. I use linux, slight changes may be needed to adapt it to Windows or to other compilers or to C++. On my machine int = 32 bits, so int is enough. Giovanni Resta 11 Jul 2013. */ // N must be 2 or 4 or 6 or 8 // I use a define since the compiler can take advantage of // an hardcoded value // size #define N 6 // number of nodes #define NN (N*N) // we already know the total number (NCYC) of Hamilton cycles // so I use this value to determine the end of the program #if N == 2 #define NCYC 1 #elif N == 4 #define NCYC 6 #elif N == 6 #define NCYC 1072 #elif N == 8 #define NCYC 4638576 #else ERROR // this will cause an error #endif // the symmetry classes counters int sym1 = 0, sym2 = 0, sym4 = 0, sym8 = 0; // Note: nodes are numbered in the obvious way from 0 to NN-1 // the neighbors of each of the NN nodes int Nei[NN][4]; // at most 4 neighbors int nNei[NN]; // actual number of neighbors // current path int Path[NN]; // Free[u]=0 if node u has already been used, Free[u]=1 otherwise int Free[NN]; // current number of cycles found unsigned nTot=0; // this part of code counts symmetries //------------------------------------------------ void Canonic(int *v, char *s); // see below // rotates by 90 degrees the cycle in array v void Rotate(int *v) { // x=v[i]%N; y=v[i]/N; for (int i=0; i> %u / %d\n",nTot,NCYC); // now I count how many different cycles I obtain by // rotating and/or mirroring the current cycle and // I update the appropriate counter (say sym4). // fist I copy the current path in p[] for (int k=0; k= (NN-N) || 0==((u+1)%N))) { for (int i=2; i=0 && (y)>=0 && (x)0) add(i,x+1,y); // I add the link to the right (but not for nodes in the last row) if (x0) add(i,x,y-1); } // all nodes are available for (int i=0; i