N皇后
N皇后问题是计算机科学中最为经典的问题之一，该问题可追溯到1848年，由国 际西洋棋棋手马克斯·贝瑟尔于提出了8皇后问题。 将N个皇后放摆放在N*N的棋盘中，互相不可攻击，有多少种摆放方式，每种摆 放方式具体是怎样的? LeetCode 51. N-Queens
皇后的攻击范围
若在棋盘上已放置一个皇后，它实 际上占据了哪些位置?
以这个皇后为中心，上、下、左、 右、左上、左下、右上、右下，8个方向的位置全部被占据。
思考: 若在棋盘上放置一个皇后，如右图 ，标记为红色位置即不可再放 其他皇后了，如何设计算法与 数据存储，实现这一过程?
方向数组：
static const int dx[]= {-1,1,0,0,-1,-1,1,1}
static const int dy[]= {0,0,-1,1,-1,1,-1,1}分别表示上，下，左，右，左上，右上，左下，右下。
第X行，y列放置皇后，mark[行][列]表示一张期盼
void put_down_the_queen(int x, int y, std::vector<std::vector<int>> & mark){
static const int dx[]= {-1,1,0,0,-1,-1,1,1}
static const int dy[]= {0,0,-1,1,-1,1,-1,1}//方向数组；
}
mark[x][y] = 1;//(x,y)放置皇后，进行标记
for(int i = 1; i < mark.size(); i++){ //8个方向，每个方向向外延伸至1至N-1
for( int j = 0; j < 8; j++){
int new_x = x + i *dx[j];
int new_y = y + i *dy[j];
if(new_x >= 0 && new_x < mark.size() && new_y >= 0 && new_y < mark.size()){
mark[new_x][new_y] = 1;
}
}
}算法设计
N皇后问题，对于N*N的棋盘，每行都要放置1个且只能放置1个皇后。 利用递归对棋盘的每一行放置皇后，放置时，按列顺序寻找可以放置皇后的列 ，若可以放置皇后，将皇后放置该位置，并更新mark标记数组，递归进行下一行的皇后放置;当该次递归结束后，恢复mark数组，并尝试下一个可能放皇后的列。 当递归可以完成N行的N个皇后放置，则将该结果保存并返回。
class Solution{
public:
std:: vector<std::vector<std::string>> solveNQueens(int n){
std::vector<std::vector<std::string>> result;//储存最终结果的数组
std::vector<std::string> location;//存储某个摆放结果，当完成一次递归找到结果后，将location push进result
std::vector<std::vector<int>> mark;//标记棋盘是否可以放置皇后的数组
for(int i = 0 ; i < n; i++){
mark.push_back((std::vector<int>()))//初始化mark
for(int j = 0;j<n;j++){
mark[i] = push_back(0);
}
location.push_back("");
location[i].append(n,'.');
}
generate(0, n, location, result, mark);
return result;
private:
void put_down_the_queen(int x, int y, std:: vector<std::vector<int>> &mark){}
}
};//k 代表完成了几个皇后的位置（正在放置第k）
void generate(int k, int n , std::vector<std::string> & location, std:: vector<std:: vector<std::vector<std:: string>>> & result, std:: vector<std::vector<int>> &mark){
if(k == n ){// 当k==n时，代表完成了第0至n-1行
result.push_back(location);//皇后的放置，所有皇后完成放置后，将记录皇后位置的location数组push进入result
return ;
}
for( int i = 0; i < n; i++){//按顺序尝试第0-n-1列
if(mark[k][i] == 0){// 如果mark[k][i] ==0,即可以放置皇后
std::vector<std::vector<int>> tmp_mark = mark;//记录回溯mark镜像
location[k][i] = 'Q';// 记录当前皇后的位置
put_down_the_queen(khi,mark);//放置皇后
generate(k+1,n,location,result,mark);//递归下一行皇后放置
mark == tmp_mark;//将mark重新赋值为回溯前状态
location =='.';
}
}
}
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.03.19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读