# 51. N-Queens

The n-queens puzzle is the problem of placing `n` queens on an `n x n` chessboard such that no two queens attack each other.

Given an integer `n`, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where `'Q'` and `'.'` both indicate a queen and an empty space, respectively.

Example 1:

``````Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
``````

Example 2:

``````Input: n = 1
Output: [["Q"]]
``````

Constraints:

• `1 <= n <= 9`

``````class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> queens(n, string(n, '.'));
dfs(0, queens, res);
return res;
}
void dfs(int row, vector<string>& queens, vector<vector<string>>& res) {
int n = queens.size();
if (row == n) {
res.push_back(queens);
return;
}
for (int j = 0; j < n; ++j) {
if (isValid(queens, row, j)) {
queens[row][j] = 'Q';
dfs(row + 1, queens, res);
queens[row][j] = '.';
}
}
}
bool isValid(vector<string>& queens, int row, int col) {
for (int i = 0; i < row; ++i) {
if (queens[i][col] == 'Q') return false;
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
if (queens[i][j] == 'Q') return false;
}
for (int i = row - 1, j = col + 1; i >= 0 && j < queens.size(); --i, ++j) {
if (queens[i][j] == 'Q') return false;
}
return true;
}
};
``````

``````class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<int> queenCol(n, -1);
dfs(0, queenCol, res);
return res;
}
void dfs(int row, vector<int>& queenCol, vector<vector<string>>& res) {
int n = queenCol.size();
if (row == n) {
vector<string> cur(n, string(n, '.'));
for (int i = 0; i < n; ++i) {
cur[i][queenCol[i]] = 'Q';
}
res.push_back(cur);
return;
}
for (int j = 0; j < n; ++j) {
if (isValid(queenCol, row, j)) {
queenCol[row] = j;
dfs(row + 1, queenCol, res);
queenCol[row] = -1;
}
}
}
bool isValid(vector<int>& queenCol, int row, int col) {
for (int i = 0; i < row; ++i) {
if (col == queenCol[i] || abs(row - i) == abs(col - queenCol[i])) return false;
}
return true;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/51

N-Queens II

Grid Illumination

https://leetcode.com/problems/n-queens/

http://www.cnblogs.com/TenosDoIt/p/3801621.html

https://leetcode.com/problems/n-queens/discuss/19805/My-easy-understanding-Java-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation