From ce9964a1630d51399cc0fab55b598743ec522419 Mon Sep 17 00:00:00 2001
From: Matthias Braun <matze@braunis.de>
Date: Thu, 7 Sep 2006 11:52:02 +0000
Subject: [PATCH] manually optimized queens

---
 ir/be/test/queens-handoptimized.c | 111 ++++++++++++++++++++++++++++++
 1 file changed, 111 insertions(+)
 create mode 100644 ir/be/test/queens-handoptimized.c

diff --git a/ir/be/test/queens-handoptimized.c b/ir/be/test/queens-handoptimized.c
new file mode 100644
index 000000000..b9bf0c147
--- /dev/null
+++ b/ir/be/test/queens-handoptimized.c
@@ -0,0 +1,111 @@
+/*
+ * Project:     GCC-firm
+ * File name:   test/Queens.c
+ * Purpose:     solve the queens problem
+ * Author:      Markus Armbruster (in sather-k)
+ * Modified by: Michael Beck (for GCC-firm)
+ * Created:     XX.11.2001
+ * CVS-ID:      $Id$
+ * Copyright:   (c) 2001 Universitaet Karlsruhe
+ * Licence:
+ */
+/*
+  -- The notorious n-queens problem (C.F. Gauss, 1850)
+  -- Copyright (C) 1996 Markus Armbruster
+*/
+
+#include <stdlib.h>
+#include <stdio.h>
+
+
+typedef int boolean;
+
+#define true	1
+#define false	0
+
+//static int *row;
+// queen in column c is at row[c]
+
+static inline int myabs(int i) {
+    if(0 > i)
+        i = -i;
+    return(i);
+}
+
+static inline boolean place_ok (int i, const int *r, int ri) {
+    // return whether queen in column i is
+    // not in check from queens left of it
+    int j = 0;
+    boolean res;
+
+    while (j < i) {
+        if ((r[j] == ri) || ((myabs(ri-r[j])) == (i-j))) {
+            res = false;
+            return(res);
+        }
+        j = j+1;
+    }
+
+    res = true;
+    return(res);
+}
+
+int solve (int n) {
+    // return the number of solutions to the n-queens problem
+    int c = 0;
+    int res = 0;
+	int *row;
+
+    row = malloc(sizeof(*row) * n);
+    row[0] = -1;
+    while (c >= 0) {
+		int ri;
+#if 1
+        do {
+            row[c] = ri = row[c]+1;
+        } while ((ri < n) && (!place_ok(c, row, ri)));
+#else
+        row[c] = row[c]+1;
+        while ((row[c] < n) && (!place_ok(c, row))) {
+            row[c] = row[c]+1;
+        }
+#endif
+        if (row[c] < n) { // successfully placed at (c,row[c])
+            if (c == n-1)
+                res = res+1;
+            else {
+                c = c+1;
+                row[c] = -1;
+            }
+        }
+        else // dead end, track back
+            c = c-1;
+    }
+    free(row);
+
+    return(res);
+}
+
+static void usage (const char *progname) {
+    printf("usage: %s\n", progname);
+}
+
+
+int main (int argc, char *argv[]) {
+    int n;
+
+    switch (argc) {
+    case 1:
+        n = 8;
+        break;
+    case 2:
+        n = atoi(argv[1]);
+        break;
+    default:
+        usage("queens");
+        return 0;
+    }
+    printf("The %d-queens problem has %d solutions.\n", n, solve(n));
+
+    return 0;
+}
-- 
2.20.1