minic/test/queen.c

   1 int printf();
   2 void *calloc();
   3 int atoi();
   4
   5 int Q;
   6 int N;
   7 int **t;
   8
   9 print() {
  10         int x;
  11         int y;
  12
  13         for (y=0; y<Q; y++) {
  14                 for (x=0; x<Q; x++)
  15                         if (t[x][y])
  16                                 printf(" Q");
  17                         else
  18                                 printf(" .");
  19                 printf("\n");
  20         }
  21         printf("\n");
  22 }
  23
  24 chk(int x, int y) {
  25         int i;
  26         int r;
  27
  28         for (r=i=0; i<Q; i++) {
  29                 r = r + t[x][i];
  30                 r = r + t[i][y];
  31                 if (x+i < Q & y+i < Q)
  32                         r = r + t[x+i][y+i];
  33                 if (x+i < Q & y-i >= 0)
  34                         r = r + t[x+i][y-i];
  35                 if (x-i >= 0 & y+i < Q)
  36                         r = r + t[x-i][y+i];
  37                 if (x-i >= 0 & y-i >= 0)
  38                         r = r + t[x-i][y-i];
  39         }
  40         return r;
  41 }
  42
  43 go(int y) {
  44         int x;
  45
  46         if (y == Q) {
  47                 print();
  48                 N++;
  49                 return 0;
  50         }
  51         for (x=0; x<Q; x++)
  52                 if (chk(x, y) == 0) {
  53                         t[x][y]++;
  54                         go(y+1);
  55                         t[x][y]--;
  56                 }
  57 }
  58
  59 main(int ac, void **av) {
  60         int i;
  61
  62         Q = 8;
  63         if (ac >= 2)
  64                 Q = atoi(av[1]);
  65         t = calloc(Q, sizeof(int *));
  66         for (i=0; i<Q; i++)
  67                 t[i] = calloc(Q, sizeof(int));
  68         go(0);
  69         printf("found %d solutions\n", N);
  70 }