题目:
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n
个皇后放置在 n×n
的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n
,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q'
和 '.'
分别代表了皇后和空位。
示例 1:
输入:n = 4 输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1 输出:[["Q"]]
提示:
1 <= n <= 9
该问题为典型的回溯问题,来看看代码吧
class Solution {
public:
void put_queen(int x,int y,vector<vector<int>>&attack)//x,y分别表示传进去的行和列,attack数组表示该行皇后可以攻击到的位置
{static const int dx[]={-1,1,0,0,-1,-1,1,1};static const int dy[]={0,0,-1,1,-1,1,-1,1};attack[x][y]=1;for(unsigned int i=1;i<attack.size();i++){for(int j=0;j<8;j++){unsigned int nx=x+i*dx[j];unsigned int ny=y+i*dy[j];if(nx>=0&&nx<attack.size()&&ny>=0&&ny<attack.size()){attack[nx][ny]=1;}}}
}
//line表示当前处理的行,n表示N皇后问题,queen数组表示皇后存储的位置,attack表示皇后攻击的位置,re表示存储N皇后的全部解法
void backtrack(int line,int n,vector<string>&queen,vector<vector<int>>&attack,vector<vector<string>>&re)
{if(line==n){re.push_back(queen);return;}for(int i=0;i<n;i++){if(attack[line][i]==0){vector<vector<int>> temp=attack;queen[line][i]='Q';put_queen(line,i,attack);backtrack(line+1,n,queen,attack,re);attack=temp;queen[line][i]='.';}}
}vector<vector<string>> solveNQueens(int n) {vector<vector<string>> re;//存储最终结果vector<vector<int>> attack;//标记皇后攻击位置vector<string>queen;//保存皇后位置for(int i=0;i<n;i++){attack.push_back((std::vector<int>()));for(int j=0;j<n;j++)attack[i].push_back(0);queen.push_back("");queen[i].append(n,'.');}backtrack(0,n,queen,attack,re);return re;}
};
这里我把题目链接贴上供各位查看
https://leetcode.cn/problems/n-queens/