# LeetCode51. N-Queens（递归 / 回溯）

## LeetCode51. N-Queens（递归 / 回溯）

• Hard
• Accepted：135,267
• Submissions：351,395

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

Given an integer n, return all distinct solutions to the n-queens puzzle.

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:

Input: 4
Output: [
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

### 链接

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

### 题解

(0, 0)(0, 1)(0,2)(0,3)
(1, 0)(1, 1)(1, 2)(1, 3)
(2, 0)(2, 1)(2, 2)(2, 3)
(3, 0)(3, 1)(3, 2)(3, 3)

### 代码

Time SubmittedStatusRuntimeMemoryLanguage
11 hours agoAccepted12 ms10.4 MBcpp
class Solution {
private:
vector<vector<string>> ans;
vector<bool> vis, dia1, dia2;
vector<string> trans(vector <int> & row)
{
int n = row.size();
vector<string> board(n, string(n, '.'));
for (int i = 0; i < n; ++i)
board[i][row[i]] = 'Q';
return board;
}
void solve(int n, int index, vector <int> & row)
{
if (index == n)
{
ans.push_back(trans(row));
return ;
}
for (int i = 0; i < n; ++i)
{
if (!vis[i] && !dia1[index + i] && !dia2[index - i + n - 1])
{
row.push_back(i);
vis[i] = true;
dia1[index + i] = true; // 对角线
dia2[index - i + n - 1] = true;
solve(n, index + 1, row);
vis[i] = false;
dia1[index + i] = false;
dia2[index - i + n - 1] = false;
row.pop_back();
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
ans.clear();
vis = vector<bool>(n + 1, false);
dia1 = vector<bool>(2*n + 1, false);
dia2 = vector<bool>(2*n + 1, false);
vector<int> row;
solve(n, 0, row);
return ans;
}
};

The end.
2019年4月14日 星期日