Skip to content

Instantly share code, notes, and snippets.

@oHaiyang
Last active August 29, 2015 14:06
Show Gist options
  • Save oHaiyang/55fc3acd553e477e5ca9 to your computer and use it in GitHub Desktop.
Save oHaiyang/55fc3acd553e477e5ca9 to your computer and use it in GitHub Desktop.
Dumb exploration of the N Queens Puzzle
#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();
}
#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);
}
@oHaiyang
Copy link
Author

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

@oHaiyang
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment