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.
For
example,
There
exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
思路：八皇后问题一直是一个经典的回溯算法，递归算法解决。这道题受字符串的全排列的启发——定义一个数组data[n],数组中第i个数组表示位于第i行的皇后的列号。先把数组data的n个数字初始化分别用0~n-1初始化，接下来就是对数组data做全排列。我们只需要判断每一个排列对应的n个皇后是不是在同一对角线上，也就是对于数组的两个下标i和j，是不是j-i=abs(data[j]-data[i]).
class Solution { public: bool check(vector<int> &data,int n) { for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if((j-i)==abs(data[j]-data[i])) { return false; } } } return true; } void Permutation(vector<vector<string> > &result,vector<int> &data,int pBegin,int n) { if(pBegin==n) { if(true==check(data,n)) { vector<string> pTemp; for(int i=0;i<n;i++) { string row(n,‘.‘); row[data[i]]=‘Q‘; pTemp.push_back(row); } result.push_back(pTemp); } } else { for(int i=pBegin;i<n;i++) { swap(data[pBegin],data[i]); Permutation(result,data,pBegin+1,n); swap(data[pBegin],data[i]); } } } void Permutation(vector<vector<string> > &result,int n) { vector<int> data(n);// for(int i=0;i<n;i++) data[i]=i; Permutation(result,data,0,n); } vector<vector<string> > solveNQueens(int n) { vector<vector<string> > result; result.clear(); Permutation(result,n); return result; } };
原文：http://www.cnblogs.com/awy-blog/p/3644850.html