八皇后问题 问题求助

rockerz

回溯只需要用8!次来解。。。4万次计算而已。。

8^8可是1千600多万种结果。。这是穷举的方法。。不是递归
递归和穷举有区别。这个在放皇后之前有用notDanger去查是否可以放，不可以放就直接跳过该格子。具体多少次计算我也不大会算。但这绝对不是穷举的方法。

附上我学过的代码。

1. 
   
2. #include <cstdio>
   
3. #include <cstdlib>
   
4. #include <cstring>
   
5. 
   
6. int row[8];
   
7. int tc,a,b,solc;
   
8. 
   
9. 
   
10. bool place (int r, int c){
    
11.         for (int prev=0;prev<c;prev++){
    
12.                 if (row[prev]==r||(abs(prev-c)==abs(row[prev]-r)))return false;
    
13.         }
    
14.         return true;
    
15. }
    
16. 
    
17. void backtrack(int n){
    
18.         if (n==8){
    
19.                 printf("第%d种\n",++solc);
    
20.                 for (int j=0;j<8;j++){
    
21.                         for (int i=0;i<8;i++){
    
22.                                 if (row[i]==j)printf ("1 ");
    
23.                                 else printf("0 ");
    
24.                         }
    
25.                         printf("\n");
    
26.                 }
    
27.                
    
28.         }
    
29.        
    
30.         for (int r=0;r<8;r++){
    
31.                 if (place(r,n)){
    
32.                         row[n]=r;
    
33.                         backtrack(n+1);
    
34.                 }
    
35.         }
    
36.        
    
37. }
    
38. int main()
    
39. {
    
40.                 memset(row,0,sizeof(row));
    
41.                 solc=0;
    
42.                 backtrack(0);
    
43.         return 0;
    
44. }
    

复制代码