数据结构与算法 第34讲 八皇后问题 算法中有无用的判断

ydy

这是整个代码：

1. #include <stdio.h>
   
2. 
   
3. int count = 0;
   
4. 
   
5. int notDanger( int row, int j, int (*chess)[8] )
   
6. {
   
7.     int i, k, flag1=0, flag2=0, flag3=0, flag4=0, flag5=0;
   
8.    
   
9.     // 判断列方向
   
10.     for( i=0; i < 8; i++ )
    
11.     {
    
12.         if( *(*(chess+i)+j) != 0 )
    
13.         {
    
14.             flag1 = 1;
    
15.             break;
    
16.         }
    
17.     }
    
18.    
    
19.     // 判断左上方
    
20.     for( i=row, k=j; i>=0 && k>=0; i--, k-- )
    
21.     {
    
22.         if( *(*(chess+i)+k) != 0 )
    
23.         {
    
24.             flag2 = 1;
    
25.             break;
    
26.         }
    
27.     }
    
28.    
    
29.     // 判断右下方
    
30.     for( i=row, k=j; i<8 && k<8; i++, k++ )
    
31.     {
    
32.         if( *(*(chess+i)+k) != 0 )
    
33.         {
    
34.             flag3 = 1;
    
35.             break;
    
36.         }
    
37.     }
    
38.    
    
39.     // 判断右上方
    
40.     for( i=row, k=j; i>=0 && k<8; i--, k++ )
    
41.     {
    
42.         if( *(*(chess+i)+k) != 0 )
    
43.         {
    
44.             flag4 = 1;
    
45.             break;
    
46.         }
    
47.     }
    
48.    
    
49. //    // 判断左下方
    
50.     for( i=row, k=j; i<8 && k>=0; i++, k-- )
    
51.     {
    
52.         if( *(*(chess+i)+k) != 0 )
    
53.         {
    
54.             flag5 = 1;
    
55.             break;
    
56.         }
    
57.     }
    
58.    
    
59.     if( flag1 || flag2 || flag3 || flag4 || flag5 )
    
60.     {
    
61.         return 0;
    
62.     }
    
63.     else
    
64.     {
    
65.         return 1;
    
66.     }
    
67. }
    
68. 
    
69. // 参数row: 表示起始行
    
70. // 参数n: 表示列数
    
71. // 参数(*chess)[8]: 表示指向棋盘每一行的指针
    
72. void EightQueen( int row, int n, int (*chess)[8] )
    
73. {
    
74.     int chess2[8][8], i, j;
    
75.    
    
76.     for( i=0; i < 8; i++ )
    
77.     {
    
78.         for( j=0; j < 8; j++ )
    
79.         {
    
80.             chess2[i][j] = chess[i][j];
    
81.         }
    
82.     }
    
83.    
    
84.     if( 8 == row )
    
85.     {
    
86.         printf("第 %d 种\n", count+1);
    
87.         for( i=0; i < 8; i++ )
    
88.         {
    
89.             for( j=0; j < 8; j++ )
    
90.             {
    
91.                 printf("%d ", *(*(chess2+i)+j));
    
92.             }
    
93.             printf("\n");
    
94.         }
    
95.         printf("\n");
    
96.         count++;
    
97.     }
    
98.     else
    
99.     {
    
100.         for( j=0; j < n; j++ )
     
101.         {
     
102.             if( notDanger( row, j, chess ) ) // 判断是否危险
     
103.             {
     
104.                 for( i=0; i < 8; i++ )
     
105.                 {
     
106.                     *(*(chess2+row)+i) = 0;
     
107.                 }
     
108.                
     
109.                 *(*(chess2+row)+j) = 1;
     
110.                
     
111.                 EightQueen( row+1, n, chess2 );
     
112.             }
     
113.         }
     
114.     }
     
115. }
     
116. 
     
117. int main()
     
118. {
     
119.     int chess[8][8], i, j;
     
120.    
     
121.     for( i=0; i < 8; i++ )
     
122.     {
     
123.         for( j=0; j < 8; j++ )
     
124.         {
     
125.             chess[i][j] = 0;
     
126.         }
     
127.     }
     
128.    
     
129.     EightQueen( 0, 8, chess );
     
130.    
     
131.     printf("总共有 %d 种解决方法!\n\n", count);
     
132.    
     
133.     return 0;
     
134. }

复制代码

其中在判断皇后是不是有危险的函数中，判断了，一竖排，左上斜线，右上斜线，左下斜线，右下斜线
在这判断中，左下斜线，右下斜线  是多余的，因为我们每次都是在新的一排开始放入，下方是不可能有皇后 的，所以，不需要判断左下斜线，右下斜线  

注释掉这两个判断，程序还是正常运行的～～～～～