题目：8皇后问题

在8×8的棋盘上，放置8个皇后（棋子），使两两之间互不攻击。所谓互不攻击是说任何两个皇后都要满足：

（1）不在棋盘的同一行；

（2）不在棋盘的同一列；

（3）不在棋盘的同一对角线上。

因此可以推论出，棋盘共有8行，故至多有8个皇后，即每一行有且仅有一个皇后。这8个皇后中的每一个应该摆放在哪一列上是解该题的任务。

 

注释：递归题。

递归参数：当前行：begin；

递归出口：至多有8个皇后；

每轮操作都要判断选中位置的行、列、斜三个位置上是否有其他皇后，有则不能放，否则递归下一行——注意标记数组在每一次递归后要恢复。

代码如下：

1 #include
     
       2 int sum=0;//表共有多少种放法即结果  3 int lie[8];//代表一竖n行  4 int xie1[2*8];//代表从↖到↘对角线 5 int xie2[2*8];//代表从↘到↖对角线 6  7 void HuangHou(int begin){ 8     if(begin>8){
   //表示搜索到了第八行,说明此次为有效搜索  9         sum++;10     }else{11         for(int i=1;i<=8;i++){
   //表每次搜索都是从第一列开始的 12             if(lie[i]==0 && xie1[begin+i-1]==0 && xie2[begin-i+8]==0){13                 lie[i]=1;14                 xie1[begin+i-1]=1;15                 xie2[begin-i+8]=1;16                 HuangHou(begin+1);//搜索下一行 17                 lie[i]=0;18                 xie1[begin+i-1]=0;19                 xie2[begin-i+8]=0;20             }21         }22     } 23 }24 int main(){25     HuangHou(1);//从第一行开始搜索 26     printf("%d",sum);27     return 0;28 }