分享程序员开发的那些事...
更新时间：2022-08-22 08:19:53
9.9 设计一种算法，打印八皇后在8*8棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
类似leetcode：N-Queens
回溯法的实现代码：
#include<vector> #include<iostream> #include<string> using namespace std; bool isValid(vector<string> &path,int row,int col) { int i,j; for(j=0;j<row;j++) if(path[j][col]=='Q') return false; //由于不一定是主对角线和副对角线上的点，所以i和j的初值不能从0或者最后一个点赋值 for(i=row-1,j=col-1;i>=0&&j>=0;i--,j--) if(path[i][j]=='Q') return false; for(i=row-1,j=col+1;i>=0&&j<(int)path.size();i--,j++) if(path[i][j]=='Q') return false; return true; } void helper(int n,int start,vector<vector<string> > &res,vector<string> &path) { if(start==n) { res.push_back(path); return; } int j; for(j=0;j<n;j++) { if(isValid(path,start,j)) { path[start][j]='Q'; helper(n,start+1,res,path); path[start][j]='.'; } } } vector<vector<string> > NQueue(int n) { vector<vector<string> > res; vector<string> str(n,string(n,'.')); helper(n,0,res,str); return res; } int main() { vector<vector<string> > result=NQueue(4); for(auto a:result) { for(auto t:a) cout<<t<<endl; cout<<endl; } }