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.
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 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 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和递归的典范。这道题最让我纠结的部分在于：
要不要考虑旋转……（事实证明不需要）
如何初始化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 ; }
