n皇后 回溯法
返回一个可行解
//教材P162 n皇后 回溯法 AC
#include <iostream>
#include <cstdio>
using namespace std;
int n = 8;
int x[8]; //x[i]表示第i个皇后摆放在第i行第x[j]列的位置，初始时均为-1
int Place(int k){
for(int i=0;i<k;i++)
if(x[i] == x[k] || abs(i-k)==abs(x[i]-x[k]))
return 1;
return 0;
}
void Queen(int n) {
int k = 0;
while(k>=0){
x[k]++;
while(x[k]<n && Place(k) == 1) x[k]++;
if(x[k] < n && k==n-1){
for(int i=0;i<n;++i) cout<<x[i]+1<<" ";//打印的列号从1开始
cout<<endl;
return; // 自己：return 去掉 输出所有可行解
}
if(x[k] < n && k<n-1) k = k+1;
else x[k--] = -1;
}
cout<<"无解"<<endl;
}
int main(){
memset(x,-1, sizeof(x));
Queen(n);
} leetcode 要求用vector 二维的 输出结果 暂略
2018年武汉理工 复试笔试提努
递归版
//AC #include<iostream> #include<cmath> #define N 8 using namespace std; int queenPos[100]; //用来存放算好的皇后位置，最左上角为（0,0） int ans_num = 0; void NQueen(int k); int main() { NQueen(0); cout<<"一共有"<<ans_num<<"个可行解"<<endl; return 0; } void NQueen(int k) //在0~k-1行皇后已经摆好的情况下，摆第k行及其后的皇后 { if(k==N) //有N个皇后已经摆好 { for(int i=0;i<N;i++) cout << queenPos[i]+1 << " "; cout << endl; ans_num++; return; } for(int j=0;j<N;j++) //逐尝试第k个皇后在j列的位置 { int i; for(i=0;i<k;i++) { if(queenPos[i]==j||abs(queenPos[i]-j)==abs(k-i)) { break; } } if(i==k) { queenPos[k]=j; NQueen(k+1); // 自己：这个回溯不会修改些状态 } } }
https://leetcode-cn.com/problems/n-queens/
https://blog.csdn.net/zaixiaxiaohong/article/details/100062487