八皇后问题

同样,这也是一道比较经典的题目,在看《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;
}