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 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 Given an integer n, return all distinct solutions to the n-queens puzzle. 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively. 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

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.

约束编程：

在放置每个皇后以后增加限制。当在棋盘上放置了一个皇后后，立即排除当前行，列和对应的两个对角线。 约束编程有助于减少需要考虑情况数。

回溯法:

Q: 当选择的方案不是最优的，无法放置下一个皇后时，此时我们该怎么做？ A: 回溯。 意思是回退一步，来改变最后放置皇后的位置并且接着往下放置。如果还是不行，再 回溯。

C++

class Solution{ public: vector<vector<string>> solveNQueens(int n){ res.clear(); board = vector<string>(n,string(n,'.')); cols = vector<int>(n,0); diag1 = vector<int>(2 * n - 1, 0); diag2 = vector<int>(2 * n - 1, 0); backtrack(n, 0); return res; } private: vector<string> board; vector<int> cols; vector<int> diag1; vector<int> diag2; vector<vector<string>> res; bool available(int x, int y, int n){//约束编程，每次放皇后时都需要 判断约束条件 //(该皇后是否在其他皇后的攻击范围？) 如果在攻击范围内就返回false，表示不可以放 // 不在攻击范围内就返回true,表示可以放 return !cols[x] && !diag1 [x+y] && !diag2[x - y + n -1]; } void update(int x, int y, int n, bool isput){//约束编程，设置约束条件: 每一个皇后的行，列，对角线不能放其他皇后 cols[x] = isput; diag1[x+y] = isput; diag2[x - y + n -1] = isput; board[x][y] = isput ? 'Q' : '.'; } //Try to put the queen on y-th row void backtrack(int n, int y){ if(y == n){ //found it res.push_back(board); return; } //try evert column for(int x = 0; x < n; x++){ if(!available(x,y,n)) continue; update(x,y,n,true); backtrack(n,y+1); update(x,y,n,false); } } };