minic/test/queen.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

int printf();
void *calloc();
int atoi();

int Q;
int N;
int **t;

print() {
	int x;
	int y;

	for (y=0; y<Q; y++) {
		for (x=0; x<Q; x++)
			if (t[x][y])
				printf(" Q");
			else
				printf(" .");
		printf("\n");
	}
	printf("\n");
}

chk(int x, int y) {
	int i;
	int r;

	for (r=i=0; i<Q; i++) {
		r = r + t[x][i];
		r = r + t[i][y];
		if (x+i < Q & y+i < Q)
			r = r + t[x+i][y+i];
		if (x+i < Q & y-i >= 0)
			r = r + t[x+i][y-i];
		if (x-i >= 0 & y+i < Q)
			r = r + t[x-i][y+i];
		if (x-i >= 0 & y-i >= 0)
			r = r + t[x-i][y-i];
	}
	return r;
}

go(int y) {
	int x;

	if (y == Q) {
		print();
		N++;
		return 0;
	}
	for (x=0; x<Q; x++)
		if (chk(x, y) == 0) {
			t[x][y]++;
			go(y+1);
			t[x][y]--;
		}
}

main(int ac, void **av) {
	int i;

	Q = 8;
	if (ac >= 2)
		Q = atoi(av[1]);
	t = calloc(Q, sizeof(int *));
	for (i=0; i<Q; i++)
		t[i] = calloc(Q, sizeof(int));
	go(0);
	printf("found %d solutions\n", N);
}