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)
9 * Copyright: (c) 2001 Universitaet Karlsruhe
13 -- The notorious n-queens problem (C.F. Gauss, 1850)
14 -- Copyright (C) 1996 Markus Armbruster
27 // queen in column c is at row[c]
29 static int myabs(int i) {
35 static boolean place_ok (int i) {
36 // return whether queen in column i is
37 // not in check from queens left of it
42 if ((row[j] == row[i]) || ((myabs(row[i]-row[j])) == (i-j))) {
52 static int solve (int n) {
53 // return the number of solutions to the n-queens problem
57 row = (void *)malloc(sizeof(*row) * n);
61 while ((row[c] < n) && (!place_ok(c))) {
64 if (row[c] < n) { // successfully placed at (c,row[c])
72 else // dead end, track back
80 static void usage (const char *progname) {
81 printf("usage: %s [n]\n", progname);
85 int main (int argc, char *argv[]) {
99 printf("The %d-queens problem has %d solutions.\n", n, solve(n));