N-Queens I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/n-queens/

题目：
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.."]
 ]
 Solution: Recursion (DFS). Use bit-manipulation solution (See N-QueensII for more details).

代码：

 class Solution {  
 public:  
   vector<vector<string> > solveNQueens(int n) {  
     vector<vector<string> > result;  
     vector<string> onePath;  
     solveNQueensHelper(n, 0, 0, 0, onePath, result);  
     return result;  
   }  
     
   // col: 第几列被占据; ld: 左45度对角线被占据; rd: 右45度对角线被占据  
   void solveNQueensHelper(int n, int col, int ld, int rd, vector<string> &onePath,   
     vector<vector<string> > &result) {  
     if (col == (1 << n) - 1) { // all cols are full 1111  
       result.push_back(onePath);  
       return;  
     }  
     int avail = ~(col | ld | rd); // find all available positions  
     for (int i = n - 1; i >= 0; --i) { // n =4, start 'Q...'   
       int pos = 1 << i;  
       if (avail & pos) {  
         string s(n, '.');  
         s[i] = 'Q';  
         onePath.push_back(s);  
         solveNQueensHelper(n, col | pos, (ld | pos) << 1, (rd | pos) >> 1, onePath, result);   
         onePath.pop_back();  
       }  
     }  
   }  
 };