N皇后问题

•问题描述

　　在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后，任何2个皇后不妨在同一行或同一列或同一斜线上。

•算法分析

      只考虑第i个皇后放置在第i行的哪一列，所以在放置第i个皇后的时候，可以从第1列判断起，如果可以放置在第1个位置，则跳到下一行放置下一个皇后。如果不能，则跳到下一列...直到最后一列，如果最后一列也不能放置，则说明此时放置方法出错，则回到上一个皇后向之前放置的下一列重新放置。

      当第n个皇后放置成功后，即得到一个可行解，此时再回到上一个皇后重新放置寻找下一个可行解...如此后，即可找出一个n皇后问题的所有可行解。

•解空间

     4*4国际象棋盘，4个皇后

•算法分析

     深度优先遍历

     剪枝函数

        约束函数

 　　　if((col[k] - col[i])*(fabs(col[k] - col[i]) - fabs(k - i))!=0)，即当之前所有皇后与皇后i不在同一水平、垂直方向，也不在对角线方向上时，可以在当前位置放置皇后i，否则考虑下一个位置

1 void Queen(int i,int n){ 2     if(i > n) 3         Output(); 4     else{ 5         for(int j=1;j<=n;++j){ 6             int k = 1; 7             col[i] = j; 8             while(k < i){ 9             if((col[k] - col[i])*(fabs(col[k] - col[i]) - fabs(k - i))!=0){10             k++;11             if(k == i)12                 Queen(i+1, n);13              }14             else{15             break;16             }17               }18         }19     }20 }

 

•小结

     算法效率

        时间复杂度分析

     深度优先遍历

     剪枝函数

        约束函数：判断皇后是否处于同一水平、垂直、对角线方向

     迭代回溯

•同学的完整代码

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int path[110]; 7 int row[110],n,m,cnt; 8 bool judge(int x) 9 {10     for(int i=1;i
          
           m)17     {18         for(int i=1;i<=m;i++)19         printf("%d ",row[i]);20         printf("\n");21         cnt++;22         return;23     }24     for(int i=1;i<=n;i++)25     {26         row[x]=i;27         if(judge(x))28         dfs(x+1);29     }30 }31 int main()32 {33     while(scanf("%d%d",&n,&m)!=EOF)34     {35         memset(path,0,sizeof(path));36         memset(row,-1,sizeof(row));37         cnt=0;38         dfs(1);39         printf("%d\n",cnt);40     }41     return 0;42 }