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