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

void queen1(int i, int num, int *q);
void queen2(int i, int num, int *q, int *c);
void queen3(int i, int num, int *q, int *c, int *l, int *r, int mode);
void queensolve(int num, int *q, int *c, int *l, int *r);

void print(int num, int *q);
void check(int num, int *q);

int sn = 0; /* 解カウンター */
int t = 0; /* 試行回数カウンター */

int main(int argc, char *argv[])
{
	int *q, *c, *l, *r;
	int num, i;
	
	if (argc < 2) {
		fprintf(stderr, "Usage: %s n [1-3]\n", argv[0]);
		exit(1);
	}

	num = atoi(argv[1]);

	q = (int*)malloc(sizeof(int) * num);
	c = (int*)malloc(sizeof(int) * num);
	l = (int*)malloc(sizeof(int) * 2 * num);
	r = (int*)malloc(sizeof(int) * 2 * num);
	
	for (i = 0; i < num; i++) {
		q[i] = c[i] = 0;
	}
	for (i = 0; i < 2 * num; i++) {
		l[i] = r[i] = 0;
	}

	if (argc == 2) {
		queen3(0, num, q, c, l, r, 1);
	}
	else {
		switch (atoi(argv[2])) {
		case 1:
			queen1(0, num, q);
			break;
		case 2:
			queen2(0, num, q, c);
			break;
		case 3:
			queen3(0, num, q, c, l, r, 1);
			break;
		default : 
			queensolve(num, q, c, l, r);
		}
	}

	
	printf("%d女王 解%d個 試行回数%d回\n", num, sn, t);
	if (sn != 0) {
		printf("試行回数/解 %d\n", t/sn);
	}
	
	free(q);
	free(c);
	free(l);
	free(r);
	
	return 0;
}


/* 解のチェック (生成後検査法にて使用) */
void check(int num, int *q)
{
	int i, j, n;

	int *c_c;
	int *c_r;
	int *c_l;
	
	c_c = (int*)malloc(sizeof(int) * num);
	c_r = (int*)malloc(sizeof(int) * 2 * num);
	c_l = (int*)malloc(sizeof(int) * 2 * num);

	n = 0;

	for (i = 0; i < num; i++) {
		c_c[i] = 0;
	}
	for (i = 0; i < 2 * num; i++) {
		c_r[i] = c_l[i] = 0;
	}
	
	for (i = 0; i < num; i++) {
		for (j = 0; j < num; j++) {
			if (q[i] == j && c_c[j] == 0 &&
				c_r[i + j] == 0 && c_l[i - j + num - 1] == 0) {

				c_c[j] = 1;
				c_r[i + j] = 1;
				c_l[i - j + num - 1] = 1;
				
				n++;
			}
		}

	}

	if (n == num) {
		++sn;
		print(num, q);
	}
	
	free(c_c);
	free(c_l);
	free(c_r);
}

/* 盤面の表示 */
void print(int num, int *q)
{
	int i, j;
	int x, y;


	printf(" 解%d %d試行\n", sn, t);
	
	for (i = 0; i < num; i++) {
		for (j = 0; j < num; j++) {
			if (q[i] == j) {
				printf(" Q");
			}
			else {
				printf(" .");
			}
		}
		printf("\n");
	}
	printf("\n");


}

/* クイーンを配置 各列にクイーン(生成後検査法1) */
void queen1(int i, int num, int *q)
{
	int j;
	
	for (j = 0; j < num; j++) {
		q[i] = j;

		if (i == (num - 1)) {
			t++;
			check(num, q);
		}
		else queen1(i + 1, num, q);

	}
}

/* クイーンを配置 各行各列にクイーン(生成後検査法2) */
void queen2(int i, int num, int *q, int *c)
{
	int j;
	
	for (j = 0; j < num; j++) {
		if (c[j] == 0) {
			q[i] = j;
			c[j] = 1;

			if (i == (num - 1)) {
				t++;
				check(num, q);
			}
			else queen2(i + 1, num, q, c);
			c[j] = 0;
		}
	}
}

/* クイーンを配置 斜めも考慮(バックトラック法) */
void queen3(int i, int num, int *q, int *c, int *l, int *r, int mode)
{
	int j;
	
	for (j = 0; j < num; j++) {
		if (c[j] == 0 && r[i + j] == 0 && l[i - j + num - 1] == 0) {
			q[i] = j;
			c[j] = r[i + j] = l[i - j + num - 1] = 1;

			if (i == (num - 1)) {
				t++;
				sn++;
				if (mode == 1) {
					print(num, q);
				}
			}
			else queen3(i + 1, num, q, c, l, r, mode);

			c[j] = r[i + j] = l[i - j + num - 1] = 0;
			
		}
	}
}

/* 1-n女王問題の解の数を求める */
void queensolve(int num, int *q, int *c, int *l, int *r)
{
	int i;
	
	for (i = 0; i < num; i++) {
		q[i] = c[i] = 0;
	}
	for (i = 0; i < 2 * num; i++) {
		l[i] = r[i] = 0;
	}

	for (i = 1; i <= num; i++) {
		sn = 0;
		queen3(0, i, q, c, l, r, 0);
		printf("%d\t%d\n", i, sn);
	}
	
	free(q);
	free(c);
	free(l);
	free(r);

	exit(0);
}