nsz Git - libfirm/blob - ir/be/test/queens-handoptimized.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 #define static
  27
  28 //static int *row;
  29 // queen in column c is at row[c]
  30
  31 static inline int myabs(int i) {
  32     if(0 > i)
  33         i = -i;
  34     return(i);
  35 }
  36
  37 static inline boolean place_ok (int i, const int *r, int ri) {
  38     // return whether queen in column i is
  39     // not in check from queens left of it
  40     int j = 0;
  41     boolean res;
  42
  43 #if 0
  44         if(0 >= i)
  45                 return true;
  46
  47         do {
  48                 int rj = r[j];
  49         if ((rj == ri) || ((myabs(ri-rj)) == (i-j))) {
  50             res = false;
  51             return(res);
  52         }
  53         j = j+1;
  54     } while(j < i);
  55
  56     res = true;
  57     return(res);
  58 #else
  59     while (j < i) {
  60                 int rj = r[j];
  61         if ((rj == ri) || ((myabs(ri-rj)) == (i-j))) {
  62             res = false;
  63             return(res);
  64         }
  65         j = j+1;
  66     }
  67
  68     res = true;
  69     return(res);
  70 #endif
  71 }
  72
  73 int solve (int n) {
  74     // return the number of solutions to the n-queens problem
  75     int c = 0;
  76     int res = 0;
  77     int *row;
  78
  79     row = malloc(sizeof(*row) * n);
  80     row[0] = -1;
  81     while (c >= 0) {
  82         int rc = row[c];
  83
  84         do {
  85             rc++;
  86         } while ((rc < n) && (!place_ok(c, row, rc)));
  87
  88         if (rc < n) { // successfully placed at (c,row[c])
  89             row[c] = rc;
  90
  91             if (c == n-1)
  92                 res = res+1;
  93             else {
  94                 c = c+1;
  95                 row[c] = -1;
  96             }
  97             continue;
  98         }
  99
 100         row[c] = rc;
 101         c = c-1;
 102     }
 103     free(row);
 104
 105     return(res);
 106 }
 107
 108 static void usage (const char *progname) {
 109     printf("usage: %s\n", progname);
 110 }
 111
 112
 113 int main (int argc, char *argv[]) {
 114     int n;
 115
 116     switch (argc) {
 117     case 1:
 118         n = 8;
 119         break;
 120     case 2:
 121         n = atoi(argv[1]);
 122         break;
 123     default:
 124         usage("queens");
 125         return 0;
 126     }
 127     printf("The %d-queens problem has %d solutions.\n", n, solve(n));
 128
 129     return 0;
 130 }