nsz Git - libfirm/blob - ir/be/test/Queens.c

   1 /*
   2  * Project:     GCC-firm
   3  * File name:   test/Queens.c
   4  * Purpose:     solve the queens problem
   5  * Author:      Markus Armbruster (in sather-k)
   6  * Modified by: Michael Beck (for GCC-firm)
   7  * Created:     XX.11.2001
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2001 Universitaet Karlsruhe
  10  * Licence:
  11  */
  12 /*
  13   -- The notorious n-queens problem (C.F. Gauss, 1850)
  14   -- Copyright (C) 1996 Markus Armbruster
  15 */
  16
  17 #include <stdlib.h>
  18 #include <stdio.h>
  19
  20
  21 typedef int boolean;
  22
  23 #define true    1
  24 #define false   0
  25
  26 static int *row;
  27 // queen in column c is at row[c]
  28
  29 static int myabs(int i) {
  30   if(0 > i)
  31     i = -i;
  32   return(i);
  33 }
  34
  35 boolean place_ok (int i) {
  36   // return whether queen in column i is
  37   // not in check from queens left of it
  38   int j = 0;
  39   boolean res;
  40
  41   printf("POK: %d\n", i);
  42
  43   while (j < i) {
  44     if ((row[j] == row[i]) || ((myabs(row[i]-row[j])) == (i-j))) {
  45                 printf("F\n");
  46       res = false;
  47       return(res);
  48     }
  49     j = j+1;
  50   }
  51   printf("T\n");
  52   res = true;
  53   return(res);
  54 }
  55
  56 int solve (int n) {
  57         // return the number of solutions to the n-queens problem
  58         int c = 0;
  59         int res = 0;
  60
  61         row = (void *)malloc(sizeof(*row) * n);
  62         row[0] = -1;
  63         while (c >= 0) {
  64                 row[c] = row[c]+1;
  65                 while ((row[c] < n) && (!place_ok(c))) {
  66                         row[c] = row[c]+1;
  67                 }
  68                 printf("RC: %d\n", row[c]);
  69                 if (row[c] < n) { // successfully placed at (c,row[c])
  70                         if (c == n-1)
  71                                 res = res+1;
  72                         else {
  73                                 c = c+1;
  74                                 row[c] = -1;
  75                         }
  76                 }
  77                 else // dead end, track back
  78                         c = c-1;
  79         }
  80         free(row);
  81
  82         return(res);
  83 }
  84
  85 static void usage (const char *progname) {
  86   printf("usage: %s\n", progname);
  87 }
  88
  89
  90 int main (int argc, char *argv[]) {
  91   int n;
  92
  93   switch (argc) {
  94   case 1:
  95     n = 8;
  96     break;
  97   case 2:
  98     n = atoi(argv[1]);
  99     break;
 100   default:
 101     usage("queens");
 102     return 0;
 103   }
 104   printf("The %d-queens problem has %d solutions.\n", n, solve(n));
 105
 106   return 0;
 107 }