题目：

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:        static vector
     
      
        > solveNQueens(int n)        {            vector
       
        
          > ret;            if ( n==0 ) return ret;            vector
         
           tmp;            vector
          
            colUsed(n,false); vector
           
             diagUsed1(2*n-1,false); vector
            
              diagUsed2(2*n-1,false); Solution::dfs(ret, tmp, n, colUsed, diagUsed1, diagUsed2); return ret; } static void dfs( vector
             
              
                >& ret, vector
               
                & tmp, int n, vector
                
                 & colUsed, vector
                 
                  & diagUsed1, vector
                  
                   & diagUsed2 ) { const int row = tmp.size(); if ( row==n ) { ret.push_back(tmp); return; } string curr(n,'.'); for ( size_t col = 0; col
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

tips：

深搜写法：

1. 找到一个解的条件是tmp的长度等于n

2. 在一列中遍历每个位置，是否能够放置Q，并继续dfs；返回结果后，回溯tmp之前的状态，继续dfs。

一开始遗漏了对角线也不能在有超过一个Q的条件，补上之后就AC了。

========================================

第二次过这道题，string(n, '.')一直写成了string('.', n)，改过来就AC了。

class Solution {public:        vector
     
      
        > solveNQueens(int n)        {            vector
       
        
          > ret;            if ( n<1 ) return ret;            vector
         
           tmp;            vector
          
            colUsed(n, false); vector
           
             r2l(2*n-1, false); vector
            
              l2r(2*n-1, false); Solution::dfs(ret, tmp, n, colUsed, r2l, l2r); return ret; } static void dfs( vector
             
              
                >& ret, vector
               
                & tmp, int n, vector
                
                 & colUsed, vector
                 
                  & r2l, vector
                  
                   & l2r) { if ( tmp.size()==n ) { ret.push_back(tmp); return; } int r = tmp.size(); string row(n, '.'); for ( int i=0; i