Dumb exploration of the N Queens Puzzle

queens.c

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 1000

static int call_init_canvas = 0;
static int call_save_stack = 0;
static int call_add_ret = 0;
static int call_set_rock = 0;
static int call_kick_rock = 0;
static int call_place = 0;

void zero(int **X, int n)
{
	int i = 0;
	int j = 0;
	for (i=0; i<n; i++)
		for (j=0; j<n; j++)
			X[i][j] = 0;
}

void init_canvas(int ***X, int n)
{
	call_init_canvas++;
	int i = 0;
	*X = malloc(sizeof(int *) * n);
	for (i=0; i<n; i++)
		(*X)[i] = malloc(sizeof(int) * n);
	zero(*X, n);
}

void save_stack(int **X, int **S, int n, int a)
{
	call_save_stack++;
	int i = 0;
	int j = 0;

	if (a == 1) {
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				S[i][j] = X[i][j];
	} else if (a == 0) {
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				X[i][j] = S[i][j];
	}
}

void add_ret(int **X, int n, int **ret[MAXSIZE])
{
	call_add_ret++;
	int i = 0;
	int j = 0;
	int flag = 1;

	while (*ret) {
		flag = 0;
		for (i=0; i<n; i++) {
			for (j=0; j<n; j++) {
				if (X[i][j] * (*ret)[i][j] < 0) {
					flag = 1;
					break;
				}
			}
			if (flag == 1)
				break;
		}
		if (flag == 0)
			break;
		ret++;
	}

	if (flag == 1) {
		init_canvas(ret, n);
		for (i=0; i<n; i++)
			for (j=0; j<n; j++)
				(*ret)[i][j] = X[i][j];
	}
}

/* Used for debugging only */
void print(int **X, int n)
{
	int i = 0;
	int j = 0;
	for (i=0; i<n; i++) {
		for (j=0; j<n; j++)
			printf("%3d", X[i][j]);
		printf("\n");
	}
	printf("\n");
}


void output(int **X, int n)
{
	int i = 0;
	int j = 0;
	for (i=0; i<n; i++) {
		for (j=0; j<n; j++)
			if (X[i][j] > 0)
				printf("  X");
			else
				printf("  -");
		printf("\n");
	}
	printf("\n");
}

void answer(int **ret[MAXSIZE], int n)
{
	int ***start = ret;
	printf("\n");
	while (*ret) {
		output(*ret, n);
		ret++;
	}
	printf("Got %ld different solutions\n", ret - start);
}

void set_rock(int **X, int n, int i, int j, int level)
{
	call_set_rock++;
	int neg_level = level * -1;
	int k = 0;
	for (k=0; k<n; k++) {
		if (X[i][k] == 0)
			X[i][k] = neg_level;
		if (X[k][j] == 0)
			X[k][j] = neg_level;
		if (i-k >= 0 && j-k >= 0 && X[i-k][j-k] == 0)
			X[i-k][j-k] = neg_level;
		if (i+k < n && j+k < n && X[i+k][j+k] == 0)
			X[i+k][j+k] = neg_level;
		if (i-k >= 0 && j+k < n && X[i-k][j+k] == 0)
			X[i-k][j+k] = neg_level;
		if (i+k < n && j-k >= 0 && X[i+k][j-k] == 0)
			X[i+k][j-k] = neg_level;
	}
	X[i][j] = level;
}

void kick_rock(int **X, int n, int level)
{
	call_kick_rock++;
	int neg_level = level * -1;
	int i = 0;
	int j = 0;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (X[i][j] == level || X[i][j] == neg_level)
				X[i][j] = 0;
}

void place(int **X, int n, int **ret[MAXSIZE])
{
	call_place++;
	int i = 0;
	int j = 0;
	static int count = 0;
	static int level = 0;
	/* int **S; */
	/* init_canvas(&S, n); */
	level++;
	for (i=0; i<n; i++)
		for (j=0; j<n; j++) {
			if (X[i][j] == 0) {
				/* save_stack(X, S, n, 1); */
				set_rock(X, n, i, j, level);
				if (++count == n) {
					add_ret(X, n, ret);
				}
				place(X, n, ret);
				kick_rock(X, n, level);
				/* save_stack(X, S, n, 0); */
				count--;
			}
		}
	level--;
}

void queen(int n)
{
	static int **X;
	static int **ret[MAXSIZE];

	init_canvas(&X, n);

	place(X, n, ret);
	answer(ret, n);
}

void call_count(void)
{
	printf("call_init_canvas: %d\n", call_init_canvas);
	printf("call_save_stack: %d\n", call_save_stack);
	printf("call_add_ret: %d\n", call_add_ret);
	printf("call_set_rock: %d\n", call_set_rock);
	printf("call_kick_rock: %d\n", call_kick_rock);
	printf("call_place: %d\n", call_place);
}

int main()
{
	queen(8);
	call_count();
}

queens_1.c

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 1000

void output(int *X, int n)
{
	int i = 0;
	int j = 0;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++)
			if (j == X[i])
				printf("  X");
			else
				printf("  -");
		printf("\n");
	}
	printf("\n");
}

int place(int *X, int k, int n)
{
	static int count = 0;
	int i = 0;
	int j = 0;
	if (k > n) {
		count++;
		output(X, n);
	} else {
		for (i = 1; i <= n; i++) {
			for (j = 1; j < k && (X[j] != i && j+X[j] != k+i && j-X[j] != k-i); j++)
				;
			if (k == j) {
				X[k] = i;
				place(X, k+1, n);
			}
		}
	}
	return count;
}

void queen(int n)
{
	static int *X;
	int count = 0;

	X = malloc(sizeof(int) * (n+1));

	count = place(X, 1, n);
	printf("Got %d different solutions!\n", count);
}

int main()
{
	queen(8);
}

queens.c:

super slow

Got 92 different solutions
call_init_canvas: 1
call_save_stack: 0
call_add_ret: 3709440
call_set_rock: 42649392
call_kick_rock: 42649392
call_place: 42649393
./queens.out  22.57s user 0.03s system 99% cpu 22.616 total

queens_1.c

it's a much better way somehow

Got 92 different solutions!
./queens.out  0.00s user 0.00s system 21% cpu 0.019 total