一、DFS实现N皇后
1 #include<bits/stdc++.h> 2 using namespace std; 3 int ans[10];//用于存放答案 4 int tot;//方案数 5 const int n=8;//N皇后问题 6 bool check(int c, int r){//判断前r行是否合法 7 for(int i=0; i<r; i++) 8 if(ans[i]==c || (abs(ans[i]-c)==abs(i-r))) 9 return false; 10 return true; 11 } 12 void printans(){//将当前答案打印 13 cout<<"No. "<<tot<<endl;//方案数 14 for(int i=0; i<n; i++){//按要求打印方案 15 for(int j=0; j<n; j++){ 16 if(j==ans[i])cout<<1<<" "; 17 else cout<<0<<" "; 18 } 19 cout<<endl; 20 } 21 } 22 void dfs(int r){ //r代表行号的选择，c代表列号的选择 23 if(r==n){ 24 tot++; 25 printans(); 26 return; 27 } 28 for(int c=0; c<n; c++){ 29 if(check(c,r)){ //此方法验证合法性是通过函数，逐行与之前已放皇后比较，注意与下面方法的区别 30 ans[r]=c;//将列的选择放在相应行数组里来存放答案 31 dfs(r+1); 32 } 33 } 34 } 35 int main() 36 { 37 dfs(0); 38 return 0; 39 }
二、DFS+回溯 实现8皇后
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n, ans[9];//存放答案 ans[i]=j表示第i行皇后位置为第j列 4 bool u[9], f1[16], f2[16]; // 5 void pr(int d){ 6 for(int i=1; i<=d; i++)cout<<ans[i]<<" "; 7 cout<<endl; 8 return; 9 } 10 void dfs(int dep){ 11 if(dep>n)pr(dep-1); 12 for(int i=1; i<=n; i++){ //每1行都有8个位置（列）可以试放 13 if(u[i]==0 && f1[dep+i]==0 && f2[dep-i+n-1]==0){ //寻找可以放置皇后的位置:判断上方、斜线是否已被占，通过三个数组的值的判断 14 u[i]=1; f1[dep+i]=1; f2[dep-i+n-1]=1; // 宣布占领第i列，和两条斜线 15 ans[dep]=i; // 摆放皇后 16 dfs(dep+1); //继续递归放置下一行的皇后 17 u[i]=0; f1[dep+i]=0; f2[dep-i+n-1]=0; //当前皇后退出 18 } 19 } 20 } 21 int main() 22 { 23 cin>>n; 24 dfs(1); //从第1行开始放置皇后的位置 25 return 0; 26 }
补充注释：u、f1、f2数组的含义分别是什么?
1 /* 2 下面这个程序是采用递归的方法回溯解八皇后问题，我们知道，国际象棋里的皇后可以吃到与之处于同一直线上的子，包括：横线、竖线、右上至左下的斜线、左上至右下的斜线，一共四条线。而这个算法是一行一行的找合适放置皇后的位置，每行只放一个皇后，所以横线这个限制已经满足，接下来考虑另外三个限制，即： 3 竖线、右上至左下的斜线、左上至右下的斜线 4 办法就是用三个数组来记录，如下： 5 int u[N+1]; // 同栏是否有皇后，0表示没有，1表示有 6 int f1[2*N+1]; // 右上至左下是否有皇后，0表示没有，1表示有 7 int f2[2*N+1]; // 左上至右下是否有皇后，0表示没有，1表示有 8 因为N（比如N=8）皇后问题中，一共有： 9 竖线N条、 10 右上至左下的斜线2*N-1条、 11 左上至右下的斜线2*N-1条、 12 又由于这个程序中计数不是从0开始，而是从1开始的， 13 所以，u[N+1]而不是u[N]， 14 同理，f1[2*N+1]而非f1[2*N-1]，f2[2*N+1]而非f2[2*N-1] 15 这样，可以理解这三个数组的长度为什么这样设置了 16 接下来，就很容易理解这三个数组的值怎么设置了 17 例如u[i]=1，表示第i列上已经有皇后了（我们不需要理会这个皇后在第几行） 18 同理可知f1和f2的含义。 19 如果我们在棋盘的第i行，第j列放置了一个皇后， 20 那么，除了将queen[i] = j;// 设定为占用 21 我们还需将u[j] = f1[i+j] = f2[i-j+N] = 1; 22 举一个具体的例子： 23 ..Q..... 24 Q....... 25 .......Q 26 ........ 27 ........ 28 ........ 29 ........ 30 ........ 31 当前我们已经在棋盘的前3行放上了3个皇后， 32 那么，这三个数组的情况如下： 33 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 34 u: 0 1 0 1 0 0 0 0 1 35 f1: 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 36 f2: 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 37 接下来，去第4行上找一个合适的位置放置第4个皇后， 38 那么我们就必须避开前面3个皇后的影响，通过对比这三个数组即可。 39 */