(90)51. N 皇后(leetcode).

题目链接： https://leetcode-cn.com/problems/n-queens/ 难度：困难 51. N 皇后 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 提示： 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

n皇后问题 额 曾经还年轻的时候写过 回溯嘛 很常用的思路 但是在写的时候出问题了！ 我不知道怎么判断是否在同一对角线上了 。。。 首先明确 回溯法 使用集合 unordered_set <int> 保证不在同一列和同一斜线（stl还是用的少。。。） columns 保证不在同一列上 diagonal 保证不在同一正斜线上 backdiagonal 保证不在同一反斜线上 （md 我一开始想用queue 实现回溯的 结果越写越乱 然后看的题解 我好菜啊。。。）

class Solution { public: vector<vector<string>> solveNQueens(int n) { // ans 返回 vector<vector<string>> ans; // queens 记录本次的答案 vector<int> queens(n,-1); unordered_set<int> columns; unordered_set<int> diagonal; unordered_set<int> backdiagonal; solve(ans,queens,n,0,columns,diagonal,backdiagonal); return ans; } void solve(vector<vector<string>>& ans,vector<int>& queens,int n,int row,unordered_set<int>& columns,unordered_set<int>& diagonal, unordered_set<int> &backdiagonal){ if(row==n){ // 结束 答案正确 vector<string> s=getans(queens, n); ans.push_back(s); }else{ // 第row行的n种情况（列） for(int i=0;i<n;++i){ // 行 斜线 if(columns.find(i)!=columns.end()){ continue; } int diag=row-i; if(diagonal.find(diag)!=diagonal.end()){ continue; } int backdiag=row+i; if(backdiagonal.find(backdiag)!=backdiagonal.end()){ continue; } // queens 集合 queens[row]=i; columns.insert(i); diagonal.insert(diag); backdiagonal.insert(backdiag); solve(ans,queens,n,row+1,columns,diagonal,backdiagonal); // 去除 保证下次递归正确 queens[row]=-1; columns.erase(i); diagonal.erase(diag); backdiagonal.erase(backdiag); } } } // queens记录位置 转化为vector<string> vector<string> getans(vector<int> &queens,int n){ vector<string> ans; for(auto a:queens){ string s=string(n, '.'); s[a]='Q'; ans.push_back(s); } return ans; } };

还有个更好的查询方法 （大佬nb 我是想不出来的菜鸟 ） 使用二进制数 记录个坐标 写的还很清楚 题解（我感觉我会忘记的。。。） 不过设置为 int 最大长度就是64了吧

将数值(int) 写为 2 进制的 每一位代表该行的一个位置（0代变可以 1代表不可） columns 保证不在同一列上 diagonal 保证不在同一正斜线上 backdiagonal 保证不在同一反斜线上 对于 diagonal backdiagonal ，下一行的不能放皇后的位置是上一行的 diagonal 左移 和 backdiagonal 的右移 x & (−x) 可以获得 x 的二进制表示中的最低位的 1 的位置 x & (x−1) 可以将 x 的二进制表示中的最低位的 1 置成 0 class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<vector<string>> ans; vector<int> queens(n,-1); solve(ans,queens,n,0,0,0,0); return ans; } void solve(vector<vector<string>>& ans,vector<int>& queens,int n,int row,int columns,int diagonal, int backdiagonal){ if(row==n){ vector<string> s=getans(queens, n); ans.push_back(s); }else{ int pos=((1<<n)-1)&(~(columns|diagonal|backdiagonal)); while(pos!=0){ int postion=pos&(-pos); pos=pos&(pos-1); int column=__builtin_ctz(postion); queens[row]=column; solve(ans,queens,n,row+1,columns|postion,(diagonal|postion)>>1,(backdiagonal|postion)<<1); queens[row] = -1; } } } vector<string> getans(vector<int> &queens,int n){ vector<string> ans; for(auto a:queens){ string s=string(n, '.'); s[a]='Q'; ans.push_back(s); } return ans; } };