#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
void *data;
struct node *left, *right;
};
void *push(struct node **root, void *data, int n, int (*cmp)(void *, void *, int n)) {
struct node *p;
int c;
if (!*root) {
if ((p = malloc(sizeof(struct node))) == 0) {
fprintf(stderr, "cannot allocate enough memory(struct node), aborted\n");
exit(-1);
}
p->data = data;
p->left = p->right = 0;
*root = p;
return data;
}
if ((c = (*cmp)(data, (*root)->data, n)) != 0) {
if (c < 0) {
return push(&((*root)->left), data, n, cmp);
} else {
return push(&((*root)->right), data, n, cmp);
}
} else {
return (*root)->data;
}
}
void release(struct node **root) {
if (*root != 0) {
release(&((*root)->right));
release(&((*root)->left));
free((*root)->data);
free(*root);
*root = 0;
}
}
void phase2image(int *phase, int **image, int n) {
int y, x;
for (y = 0; y < n; y++) for (x = 0; x < n; x++) image[y][x] = 0;
for (x = 0; x < n; x++)
image[phase[x]][x] = 1;
}
void image2phase(int **image, int *phase, int n) {
int x, y;
for (x = 0; x < n; x++)
for (y = 0; y < n; y++)
if (image[y][x] > 0)
phase[x] = y;
}
void rotate(int *phase, int n, int **work) {
int x, y;
phase2image(phase, work, n);
for (y = 0; y < n; y++)
for (x = 0; x < n; x++)
work[n - 1 - x][y + n] = work[y] [x];
for (y = 0; y < n; y++)
for (x = 0; x < n; x++)
work[y][x] = work[y][x + n];
image2phase(work, phase, n);
}
void mirror(int *phase, int n, int **work) {
int x, y;
phase2image(phase, work, n);
for (y = 0; y < n; y++)
for (x = 0; x < y; x++) {
int t;
t = work[y][x];
work[y][x] = work[x][y];
work[x][y] = t;
}
image2phase(work, phase, n);
}
int cmp(int *p, int *q, int n) {
int i, x;
for (i = n - 1; i >= 0 && !(x = p[i] - q[i]); i--)
;
return x;
}
int checkAndRegister(int *phase, int n, int **work, struct node **root) {
int *p;
int i;
if ((p = malloc(sizeof(int) * n)) != 0) {
memcpy(p, phase, sizeof(int) * n);
if (push(root, p, n, (int (*)(void *, void *, int))cmp) != p) {
free(p);
return 0;
}
for (i = 0; i < 3; i++) {
rotate(phase, n, work);
if ((p = malloc(sizeof(int) * n)) == 0) {
goto bad_alloc;
}
memcpy(p, phase, sizeof(int) * n);
if (push(root, p, n, (int (*)(void *, void *, int))cmp) != p)
free(p);
}
#if 0
rotate(phase, n, work);
mirror(phase, n, work);
if ((p = malloc(sizeof(int) * n)) == 0) {
goto bad_alloc;
}
memcpy(p, phase, sizeof(int) * n);
if (push(root, p, n, (int (*)(void *, void *, int))cmp) != p)
free(p);
for (i = 0; i < 3; i++) {
rotate(phase, n, work);
if ((p = malloc(sizeof(int) * n)) == 0) {
goto bad_alloc;
}
memcpy(p, phase, sizeof(int) * n);
if (push(root, p, n, (int (*)(void *, void *, int))cmp) != p)
free(p);
}
#endif
} else {/* bad alloc */
bad_alloc:
fprintf(stderr, "cannnot allocate enough memory, aborted.\n");
exit(1);
}
return 1;
}
static int counter1 = 0;
static int counter2 = 0;
void output_phase(int *d, int n, int **work) {
int x, y;
for (x = 0; x < n; x++)
for (y = 0; y < n; y++)
work[y][x] = 0;
for (x = 0; x < n; x++)
work[d[x]][x] = 1;
for (y = 0; y < n; y++) {
for (x = 0; x < n; x++)
if (work[y][x])
putchar('Q');
else
putchar('.');
putchar('\n');
}
putchar('\n');
}
int noqueen(int *c, int x, int y, int n, int **work) { /* set y-pos for given x-pos */
int i, tx, ty;
if (x == 0)
return 1;
for (tx = 0; tx < n; tx++) /* clear work */
for (ty = 0; ty < n; ty++)
work[ty][tx] = 0;
for (i = 0; i < x; i++)
work[c[i]][i] = 1; /* set y-pos for given x-pos */
/* left-upper */
tx = x; ty = y;
while (tx >= 0 && ty >= 0) { tx--; ty--; }
tx++; ty++;
while (tx < x && ty < y) {
if (work[ty][tx])
return 0;
tx++; ty++;
}
/* left-downer */
tx = x; ty = y;
while (tx >= 0 && ty < n) { tx--; ty++; }
tx++; ty--;
while (tx < x && ty > y) {
if (work[ty][tx])
return 0;
tx++; ty--;
}
return 1;
}
void f(int p, int *a, int n, int **work, struct node **root) {
int i;
if (n == p) {
counter2++;
if (checkAndRegister(a + n, n, work, root)) {
printf("%d-%d\n", n, ++counter1);
output_phase(a + n, n, work);
}
} else {
int *b;
if ((b = malloc(sizeof(int) * n * 2)) != 0) {
for (i = 0; i < n; i++)
if (a[i] < 0) {
if (noqueen(a + n, p, i, n, work)) {
memcpy(b, a, sizeof(int) * n * 2);
b[i] = p;
b[n + p] = i;
f(p + 1, b, n, work, root);
}
}
free(b);
}
}
}
int main(int argc, char *argv[]) {
int *a, n, i;
int **work;
struct node *root;
/*
if (argc != 2) {
printf("usage: %s <num>\n", argv[0]);
return 1;
}
n = atoi(argv[1]);
*/
n = 8;
/* allocate work area */
if ((work = malloc(sizeof(int *) * n)) != 0) {
int k;
for (k = 0; k < n; k++) work[k] = 0;
for (k = 0; k < n; k++)
if ((work[k] = malloc(sizeof(int) * n * 2)) == 0)
break;
if (k == n) {
/*----------*/
/* start actual calcaulationg */
if ((a = malloc(sizeof(int) * n * 2)) != 0) {
for (i = 0; i < n; i++)
a[i] = -1;
counter1 = counter2 = 0;
root = 0;
f(0, a, n, work, &root);
printf("all:%d\n", counter2);
release(&root);
free(a);
}
/*----------*/
}
/* release work area */
for (k = 0; k < n; k++)
free(work[k]);
free(work);
}
return 0;
}
/* end */