51 N-Queens

Hard

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

N-Queens

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
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.

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

N-Queens

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q''.' 分别代表了皇后和空位。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

想法

经典的八皇后,DFS和递归的典范。这道题最让我纠结的部分在于:

  1. 要不要考虑旋转……(事实证明不需要)
  2. 如何初始化vector<string>

std::vector::vector的构造函数里有这么一条:

1
2
3
4
5
6
7
8
explicit vector( size_type count, 
const T& value = T(),
const Allocator& alloc = Allocator());
(until C++11)
vector( size_type count,
const T& value,
const Allocator& alloc = Allocator());
(since C++11)

也就是说可以通过vector v(count, value);来初始化vector<string>,同样的,string也支持这一构造函数,因此,通过vector<string> board(n, string(n, '.'));就可以初始化vector<string>了。

其实还可以考虑一下怎么不用递归写……大体用个队列也是可行的吧……

最后就是算行列斜线标记那一点花了一点时间,还遇到小bug……注意左斜列是$n + y - x -1$,右斜列是$x+y$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>

using namespace std;

void dfs(int n, int depth, vector<vector<string>> &res, vector<string> &board,
vector<bool> &row, vector<bool> &column, vector<bool> &rightX, vector<bool> &leftX)
{
if (depth >= n) {
res.push_back(vector<string>(board));
}
else {
for (int index = 0; index < n; index++) {
if (row[index] && column[depth] && rightX[index + depth] && leftX[depth - index + n - 1]) {
row[index] = column[depth] = rightX[index + depth] = leftX[depth - index + n - 1] = false;
board[index][depth] = 'Q';
dfs(n, depth + 1, res, board, row, column, rightX, leftX);
board[index][depth] = '.';
row[index] = column[depth] = rightX[index + depth] = leftX[depth - index + n - 1] = true;
}
}
}
}

vector<vector<string>> solveNQueens(int n)
{
vector<vector<string>> res;
vector<string> board(n, string(n, '.'));
vector<bool> row(n, true);
vector<bool> column(n, true);
vector<bool> rightX(2 * n - 1, true);
vector<bool> leftX(2 * n - 1, true);

dfs(n, 0, res, board, row, column, rightX, leftX);

return res;
}

int main(void)
{
vector<vector<string>> res = solveNQueens(8);
int count = 0;
for (vector<string> v : res) {
cout << "Case" << ++count << ":" << endl;
for (string s : v) {
cout << s << endl;
}
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×