八皇后问题

长大1/2

参考了小甲鱼的代码，虽然有些地方看不懂
这里的left函数不是必须的，只是为了严谨
花了几天时间，想出来了感觉好有成就感

1. #include <stdio.h>
   
2. #define OCUR 'O'         //该位置已有皇后
   
3. #define NOTOCUR '*'     //无皇后时数组的填充符号
   
4. #define NUM 8         //皇后个数
   
5. 
   
6. void Queen(int x,int y,char str[NUM][NUM]);// 求解函数
   
7. void print(char str[NUM][NUM]);//打印解函数
   
8. int left(int x,int y,char str[NUM][NUM]);//判断（x,y）的左侧是否已有皇后
   
9. int top(int x,int y,char str[NUM][NUM]);//判断（x,y）的上侧是否已有皇后
   
10. int left_top(int x,int y,char str[NUM][NUM]);//判断（x,y）的左上侧是否已有皇后
    
11. int right_top(int x,int y,char str[NUM][NUM]);//判断（x,y）的右上侧是否已有皇后
    
12. void init(char str[NUM][NUM]);//初始化，使棋盘上无皇后
    
13. static int count = 0;//全局变量，用于记录已求解的个数
    
14. 
    
15. int main(){
    
16.         char str[NUM][NUM];
    
17. 
    
18.         int x=0,y=0;
    
19.         while(x != NUM){
    
20.                 printf("当x=%d时---->\n",x);
    
21.                 init(str);
    
22.                 Queen(x,y,str);
    
23.                 x++;
    
24.         }
    
25.         printf("count = %d\n",count);
    
26. 
    
27.         return 0;
    
28. }
    
29. void init(char str[NUM][NUM]){
    
30.         int i,j;
    
31.         for(i=0;i<NUM;i++){
    
32.                 for(j=0;j<NUM;j++){
    
33.                         str[i][j] = NOTOCUR;
    
34.                 }
    
35.         }
    
36. }
    
37. void print(char str[NUM][NUM]){
    
38.         printf("找到第%d组:\n",count);
    
39.         int i,j;
    
40.         for(i=0;i<NUM;i++){
    
41.                 for(j=0;j<NUM;j++){
    
42.                         printf("%c ",str[j][i]);
    
43.                 }
    
44.                 putchar('\n');
    
45.         }
    
46.         printf("*******************\n");
    
47. }
    
48. void Queen(int x,int y,char str[NUM][NUM]){
    
49.         if(top(x,y,str) && left(x,y,str) && left_top(x,y,str) && right_top(x,y,str)){
    
50.                 str[x][y] = OCUR;
    
51.                 y++;
    
52.                 x=0;
    
53.                 if(y == NUM){
    
54.                         count++;
    
55.                         print(str);
    
56.                         return;
    
57.                 }
    
58.                 while(x != NUM){
    
59.                         Queen(x,y,str);
    
60.                         str[x][y] = NOTOCUR;
    
61.                         x++;
    
62.                 }
    
63.         }
    
64.        
    
65.         return;
    
66. }
    
67. int top(int x,int y,char str[NUM][NUM]){
    
68.         int j;
    
69.        
    
70.         for(j = y;j >= 0;j--){
    
71.                 if(str[x][j] == OCUR){
    
72.                         return 0;
    
73.                 }
    
74.         }
    
75.        
    
76.         return 1;
    
77. }
    
78. int left(int x,int y,char str[NUM][NUM]){
    
79.         int i;
    
80. 
    
81.         for(i = x;i >= 0;i--){
    
82.                 if(str[i][y] == OCUR){
    
83.                         return 0;
    
84.                 }
    
85.         }
    
86.        
    
87.         return 1;
    
88. }
    
89. int left_top(int x,int y,char str[NUM][NUM]){
    
90.         int i,j;
    
91. 
    
92.         for(i=x,j=y;i>=0 && j>=0;i--,j--){
    
93.                 if(str[i][j] == OCUR){
    
94.                         return 0;
    
95.                 }       
    
96.         }
    
97. 
    
98.         return 1;
    
99. }
    
100. int right_top(int x,int y,char str[NUM][NUM]){
     
101.         int i,j;
     
102. 
     
103.         for(i=x,j=y;i < NUM && j>=0;i++,j--){
     
104.                 if(str[i][j] == OCUR){
     
105.                         return 0;
     
106.                 }       
     
107.         }
     
108.        
     
109.         return 1;
     
110. }
     

复制代码