八皇后问题

发表于 | 分类于 |

同样，这也是一道比较经典的题目，在看《Python基础教程》的时候上面作为生成器一章的例子，到了这个寒假就想重新摸一下。题目也就不再叙述了。

主要的解决方式就是递归，只是通过生成器来解决变得十分地轻松了，这道题目后面想用C语言来解决一下。

通过这道题目，我以前看的python的内容基本上也全部忘了。要加快复习啊。同时，写程序的时候，数据结构真的是一件非常重要的事情。如果没有做好的话，那真的感觉下手的时候就处处碰壁啊。

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
#coding:utf-8
__author__ = 'shoumu'
import random
def conflict(state, nextX):
    nextY = len(state)
    for i in range(nextY):
        if abs(state[i] - nextX)  in (0, nextY - i):
            return True
    return False
def queens(num = 8, state = ()):
    for pos in range(num):
        if not conflict(state, pos):
            if len(state) == num - 1:
                yield (pos, )
            else:
                for result in queens(num, state + (pos, )):
                    yield (pos, ) + result
def prettyPrint(solution):
    def line(pos, length = len(solution)):
        return '.' * (pos) + 'X' + '.' * (length - pos - 1)
    for pos in solution:
        print line(pos)
# prettyPrint(random.choice(list(queens(8))))
for solution in list(queens(8)):
    prettyPrint(solution)
    print "============================"

下面是我写的一个c语言的版本，存在bug，结果会重复打印很多次，现在我想不清楚到底是什么问题，先列在这里吧。

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
#include <stdio.h>
#include <stdlib.h>
int conflict(int* array, int length, int nextY)
{
	int i;
	int nextX = length;
	for(i = 0; i < length; i ++) 
	{
		if(nextY == array[i] || abs(array[i] - nextY) == (nextX - i))
			return 1;
	}
	return 0;
}
void queens(int num, int* state, int length)
{
	int i, j;
	if(length == num)
	{
		// for(i = 0; i < num; i ++)
		// {
		// 	for(j = 0; j < state[i]; j ++)
		// 		printf(".");
		// 	printf("*");
		// 	for(j = state[i] + 1; j < num; j ++)
		// 		printf(".");
		// 	printf("\n");
		// }
		for(i = 0; i < length; i ++)
			printf("%d\t", state[i]);
		printf("\n\n");
		return;
	}
	else	
	{
		for(i = 0; i < num; i ++)
		{
			if(length == 0) 
			{
				state[0] = i;
				queens(num, state, 1);
			}
			else
			{
				for(j = 0; j < length; j ++)
				{
					if(conflict(state, length, i))
						continue;
					else
					{
						state[length] = i;
						queens(num, state, length + 1);
					}
				}
			}
		}
	}
}
int main()
{
	int array[8];
	int length = 0;
	int num = 4;
	// printf("the nums of the game: ");
	// scanf("%d", &num);
	queens(num, array, length);
	return 0;
}