fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5.  
  6. struct node {
  7.   void *data;
  8.   struct node *left, *right;
  9. };
  10.  
  11. void *push(struct node **root, void *data, int n, int (*cmp)(void *, void *, int n)) {
  12.   struct node *p;
  13.   int c;
  14.   if (!*root) {
  15.     if ((p = malloc(sizeof(struct node))) == 0) {
  16.       fprintf(stderr, "cannot allocate enough memory(struct node), aborted\n");
  17.       exit(-1);
  18.     }
  19.     p->data = data;
  20.     p->left = p->right = 0;
  21.     *root = p;
  22.     return data;
  23.   } 
  24.   if ((c = (*cmp)(data, (*root)->data, n)) != 0) {
  25.     if (c < 0) {
  26.       return push(&((*root)->left), data, n, cmp);
  27.     } else {
  28.       return push(&((*root)->right), data, n, cmp);
  29.     }
  30.   } else {
  31.     return (*root)->data;
  32.   }
  33. }
  34.  
  35. void release(struct node **root) {
  36.   if (*root != 0) {
  37.     release(&((*root)->right));
  38.     release(&((*root)->left));
  39.     free((*root)->data);
  40.     free(*root);
  41.     *root = 0;
  42.   }
  43. }
  44.  
  45. void phase2image(int *phase, int **image, int n) {
  46.   int y, x;
  47.   for (y = 0; y < n; y++) for (x = 0; x < n; x++) image[y][x] = 0;
  48.   for (x = 0; x < n; x++)
  49.     image[phase[x]][x] = 1;
  50. }
  51.  
  52. void image2phase(int **image, int *phase, int n) {
  53.   int x, y;
  54.   for (x = 0; x < n; x++)
  55.     for (y = 0; y < n; y++)
  56.       if (image[y][x] > 0)
  57.         phase[x] = y;
  58. }
  59.  
  60. void rotate(int *phase, int n, int **work) {
  61.   int x, y;
  62.   phase2image(phase, work, n);
  63.   for (y = 0; y < n; y++)
  64.     for (x = 0; x < n; x++)
  65.       work[n - 1 - x][y + n] = work[y] [x];
  66.   for (y = 0; y < n; y++)
  67.     for (x = 0; x < n; x++)
  68.       work[y][x] = work[y][x + n];
  69.   image2phase(work, phase, n);
  70. }
  71.  
  72. void mirror(int *phase, int n, int **work) {
  73.   int x, y;
  74.  
  75.   phase2image(phase, work, n);
  76.   for (y = 0; y < n; y++)
  77.     for (x = 0; x < y; x++) {
  78.       int t;
  79.       t = work[y][x];
  80.       work[y][x] = work[x][y];
  81.       work[x][y] = t;
  82.     }
  83.   image2phase(work, phase, n);
  84. }
  85.  
  86. int cmp(int *p, int *q, int n) {
  87.   int i, x;
  88.   for (i = n - 1; i >= 0 && !(x = p[i] - q[i]); i--)
  89.     ;
  90.   return x;
  91. }
  92.  
  93. int checkAndRegister(int *phase, int n, int **work, struct node **root) {
  94.   int *p;
  95.   int i;
  96.   if ((p = malloc(sizeof(int) * n)) != 0) {
  97.     memcpy(p, phase, sizeof(int) * n);
  98.     if (push(root, p, n, (int (*)(void *, void *, int))cmp) != p) {
  99.       free(p);
  100.       return 0;
  101.     }
  102.  
  103.     for (i = 0; i < 3; i++) {
  104.       rotate(phase, n, work);
  105.       if ((p = malloc(sizeof(int) * n)) == 0) {
  106.         goto bad_alloc;
  107.       }
  108.       memcpy(p, phase, sizeof(int) * n);
  109.       if (push(root, p, n, (int (*)(void *, void *, int))cmp) != p)
  110.         free(p);
  111.     }
  112.     rotate(phase, n, work);
  113.     mirror(phase, n, work);
  114.     if ((p = malloc(sizeof(int) * n)) == 0) {
  115.       goto bad_alloc;
  116.     }
  117.     memcpy(p, phase, sizeof(int) * n);
  118.     if (push(root, p, n, (int (*)(void *, void *, int))cmp) != p)
  119.       free(p);
  120.  
  121.     for (i = 0; i < 3; i++) {
  122.       rotate(phase, n, work);
  123.       if ((p = malloc(sizeof(int) * n)) == 0) {
  124.         goto bad_alloc;
  125.       }
  126.       memcpy(p, phase, sizeof(int) * n);
  127.       if (push(root, p, n, (int (*)(void *, void *, int))cmp) != p)
  128.         free(p);
  129.     }
  130.  
  131.   } else {/* bad alloc */
  132.   bad_alloc:
  133.     fprintf(stderr, "cannnot allocate enough memory, aborted.\n");
  134.     exit(1);
  135.   }
  136.   return 1;
  137. }
  138.  
  139. static int counter1 = 0;
  140. static int counter2 = 0;
  141.  
  142. void output_phase(int *d, int n, int **work) {
  143.   int x, y;
  144.   for (x = 0; x < n; x++)
  145.     for (y = 0; y < n; y++)
  146.       work[y][x] = 0;
  147.   for (x = 0; x < n; x++)
  148.     work[d[x]][x] = 1;
  149.   for (y = 0; y < n; y++) {
  150.     for (x = 0; x < n; x++)
  151.       if (work[y][x])
  152.         putchar('Q');
  153.       else
  154.         putchar('.');
  155.     putchar('\n');
  156.   }
  157.   putchar('\n');
  158. }
  159.  
  160. int noqueen(int *c, int x, int y, int n, int **work) { /* set y-pos for given x-pos */
  161.   int i, tx, ty;
  162.   if (x == 0)
  163.     return 1;
  164.   for (tx = 0; tx < n; tx++) /* clear work */
  165.     for (ty = 0; ty < n; ty++)
  166.       work[ty][tx] = 0;
  167.   for (i = 0; i < x; i++)
  168.     work[c[i]][i] = 1;  /* set y-pos for given x-pos */
  169.   /* left-upper */
  170.   tx = x; ty = y;
  171.   while (tx >= 0 && ty >= 0) { tx--; ty--; }
  172.   tx++; ty++;
  173.   while (tx < x && ty < y) {
  174.     if (work[ty][tx])
  175.       return 0;
  176.     tx++; ty++;
  177.   }
  178.   /* left-downer */
  179.   tx = x; ty = y;
  180.   while (tx >= 0 && ty < n) { tx--; ty++; }
  181.   tx++; ty--;
  182.   while (tx < x && ty > y) {
  183.     if (work[ty][tx])
  184.       return 0;
  185.     tx++; ty--;
  186.   }
  187.   return 1;
  188. }
  189.  
  190. void f(int p, int *a, int n, int **work, struct node **root) {
  191.   int i;
  192.   if (n == p) {
  193.     counter2++;
  194.     if (checkAndRegister(a + n, n, work, root)) {
  195.       ++counter1;
  196. /*      printf("%d-%d\n", n, ++counter1); */
  197. /*      output_phase(a + n, n, work);*/
  198.     }
  199.   } else {
  200.     int *b;
  201.     if ((b = malloc(sizeof(int) * n * 2)) != 0) {
  202.       for (i = 0; i < n; i++)
  203.         if (a[i] < 0) {
  204.           if (noqueen(a + n, p, i, n, work)) {
  205.             memcpy(b, a, sizeof(int) * n * 2);
  206.             b[i] = p;
  207.             b[n + p] = i;
  208.             f(p + 1, b, n, work, root);
  209.           }
  210.         }
  211.       free(b);
  212.     }
  213.   }
  214. }
  215.  
  216. int main(int argc, char *argv[]) {
  217.   int *a, n, i;
  218.   int **work;
  219.   struct node *root;
  220.   time_t t, t2;
  221.  
  222.   for(n = 1; n <= 16; n++) {
  223.     /* allocate work area */
  224.     time(&t);
  225.     printf("n: %d, ", n);
  226.     if ((work = malloc(sizeof(int *) * n)) != 0) {
  227.       int k;
  228.       for (k = 0; k < n; k++) work[k] = 0;
  229.       for (k = 0; k < n; k++)
  230.         if ((work[k] = malloc(sizeof(int) * n * 2)) == 0)
  231.           break;
  232.       if (k == n) {
  233.  
  234.       /* start actual calcaulationg */
  235.         if ((a = malloc(sizeof(int) * n * 2)) != 0) {
  236.           for (i = 0; i < n; i++)
  237.             a[i] = -1;
  238.           counter1 = counter2 = 0;
  239.           root = 0;
  240.           f(0, a, n, work, &root);
  241.           printf("uniq: %d, all:%d, ", counter1, counter2);
  242.           printf("time: %d\n", time(&t2) - t); fflush(stdout);
  243.           release(&root);
  244.           free(a);
  245.         }
  246.       }
  247.       /* release work area */
  248.       for (k = 0; k < n; k++)
  249.         free(work[k]);
  250.       free(work);
  251.     }
  252.   }
  253.   return 0;
  254. }
  255. /* end */
  256.  
Time limit exceeded #stdin #stdout 5s 7448KB
comments (?)
stdin 
Standard input is empty
stdout 
n: 1, uniq: 1, all:1, time: 0
n: 2, uniq: 0, all:0, time: 0
n: 3, uniq: 0, all:0, time: 0
n: 4, uniq: 1, all:2, time: 0
n: 5, uniq: 2, all:10, time: 0
n: 6, uniq: 1, all:4, time: 0
n: 7, uniq: 6, all:40, time: 0
n: 8, uniq: 12, all:92, time: 0
n: 9, uniq: 46, all:352, time: 0
n: 10, uniq: 92, all:724, time: 0
n: 11, uniq: 341, all:2680, time: 0
n: 12, uniq: 1787, all:14200, time: 1
https://ideone.com/I1rOrI
language:
C (gcc 8.3)
created:
8 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!