本文共 978 字，大约阅读时间需要 3 分钟。

问题：

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后，任何2个皇后不妨在同一行或同一列或同一斜线上。

解答：

深搜。

代码：

class Solution {  public:	  vector
   
    
      > solveNQueens(int n) {		  vector
     
      
        > res;		  vector
       
         temp;		  search(0, n, temp, res);		  return res;	  }  private:	  void search(int level, int n, vector
        
          &temp, vector
         
          
            > &res) { if (level == n) { if (find(res.begin(), res.end(), temp) == res.end()) res.push_back(temp); return; } string str (n, '.'); for(int i = 0; i < n; i++) { str[i] = 'Q'; if (judge(i, temp)) { temp.push_back(str); search(level + 1, n, temp, res); temp.pop_back(); } str[i] = '.'; } } bool judge(int pos, vector
           
             &temp) { for (int i = 0; i < temp.size(); i++) { if (temp[i][pos] == 'Q') { return false; } for (int j = 0; j < temp[i].length(); j++) { if (temp[i][j] == 'Q') { if (abs(int(temp.size()) - i) == abs(j - pos)) return false; } } } return true; } };
           
          
         
        
       
      
     
    
   

待续

转载地址：http://aytsi.baihongyu.com/