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.."] ]
思路：主要思路见http://blog.csdn.net/hackbuteer1/article/details/6657109。主要代码与博主的第一段非递归代码类似。原博的第32行判断似乎有问题。
1 class Solution { 2 public: 3 vector<vector<string> > result; 4 int queen_num_; 5 vector<vector<string>> solveNQueens(int n) { 6 vector<int> a(n, -1); 7 queen_num_ = n; 8 solveNQueens(a); 9 10 return result; 11 } 12 13 bool IsValid(const vector<int>& a, int row, int col) { 14 for (int i = 0; i < row; i++) { 15 if (col == a[i] || abs(i - row) == abs(a[i] - col)) 16 return false; 17 } 18 19 return true; 20 } 21 22 void solveNQueens(vector<int>& a) { 23 int i = 0, j = 0; 24 while (i < queen_num_) { 25 while (j < queen_num_) { 26 if (IsValid(a, i, j)) { 27 a[i] = j; 28 j = 0; 29 break; 30 } else { 31 j++; 32 } 33 } 34 35 if (a[i] == -1) { 36 if (i == 0) { 37 return; 38 } else { 39 i--; 40 j = a[i] + 1; 41 a[i] = -1; 42 continue; 43 } 44 } 45 46 if (i == queen_num_ - 1) { 47 string s(queen_num_, ‘.‘); 48 vector<string> sol(queen_num_, s); 49 50 for (int i = 0; i < queen_num_; i++) 51 sol[i][a[i]] = ‘Q‘; 52 53 result.push_back(sol); 54 j = a[i] + 1; 55 a[i] = -1; 56 continue; 57 } 58 i++; 59 }//while (i < queen_num_); 60 }//solveNQueens 61 };
扩展阅读：
1.
原文：http://www.cnblogs.com/vincently/p/4714230.html