N-Queens II

来源：Leetcode

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

题目：
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.."]
 ]

代码：

 class Solution {  
 public:  
   //Version 1: recursion  
   int totalNQueens(int n) {  
     vector<int> board(n, -1); // store board (col) configuration from row 0...n-1.  
     int res = 0;  
     totalNQueensHelper(n, 0, board, res);  
     return res;  
   }  
     
   void totalNQueensHelper(int n, int row, vector<int>& board, int &res) {  
     if(row == n) {  
       res++;  
       return;  
     }  
     for(int i = 0; i < n; ++i) {  
       if(isValid(board, row, i)) {  
         board[row] = i;  
         totalNQueensHelper(n, row + 1, board, res);  
         board[row] = -1;  
       }  
     }  
   }  
     
   bool isValid(vector<int>& board, int row, int col) {  
     for (int i = 0; i < row; ++i) {  
       if (board[i] == col || row - i == abs(col - board[i])) {  
         return false;                
       }  
     }  
     return true;  
   }  
 };  
   
 class Solution {  
 public:   
   //Version 2: Bit version  
   int totalNQueens(int n) {  
     int result = 0;  
     totalNQueensHelp(n, 0, 0, 0, result);  
     return result;  
   }  
   
   void totalNQueensHelp(int n, int col, int ld, int rd, int &result) {  
     if (col == (1 << n) - 1) {  
       result++;  
       return;  
     }  
     int avail = ~(col | ld | rd);  
     for (int i = n - 1; i >= 0; --i) {  
       int pos = 1 << i;  
       if (avail & pos) {  
         totalNQueensHelp(n, col | pos, (ld | pos) << 1, (rd | pos) >> 1, result);          
       }  
     }  
   }  
 };