一. 题目描述

The n-queens puzzle is the problem of placing n queens on an nn 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.<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPkZvciBleGFtcGxlLCBUaGVyZSBleGlzdCB0d28gZGlzdGluY3Qgc29sdXRpb25zIHRvIHRoZSA0LXF1ZWVucyBwdXp6bGU6PC9wPg0KPHByZSBjbGFzcz0="brush:java;"> [ [.Q.., // Solution 1 ...Q, Q..., ..Q.], [..Q., // Solution 2 Q..., ...Q, .Q..] ]

二. 题目分析

著名的N皇后问题，题目的意思是在一个n×n棋盘中，每行放一个棋子，使得棋子所在的列和两条斜线上没有其他棋子，打印所有可能。

使用深搜dfs去遍历，考虑所有可能，row中标记每一行摆放棋子的对应下标的元素，col记录当前列是否已有棋子，对角线的判断就是两点行差值和列差值是否相同。

当dfs深度达到n时，意味着已经可以遍历完最低一层，存在满足条件的解，把矩阵中个元素的信息转化为'.'或'Q'，存到结果中。

三. 示例代码

// 来源:http://blog.csdn.net/havenoidea/article/details/12167399
#include 
   
     #include 
    
      using namespace std; class Solution { public: vector
     
       > solveNQueens(int n) { this->row = vector
      
       (n, 0); // 行信息 this->col = vector
       
        (n, 0); // 列信息 dfs(0, n, result); // 深搜 return result; } private: vector
        
          > result; // 存放打印的结果 vector
         
           row; // 记录每一行哪个下标是Q vector
          
            col; // 记录每一列是否已有Q void dfs(int r, int n, vector
           
             > & result) // 遍历第r行，棋盘总共有n行 { if (r == n) // 可遍历到棋盘底部，填入本次遍历结果 { vector
            
              temp; for (int i = 0; i < n; ++i) { string s(n, '.'); // 每行先被初始化为'.' s[row[i]] = 'Q'; // 每行下标被标记为1的元素被标记为Q temp.push_back(s); } result.push_back(temp); } int i, j; for (i = 0; i < n; ++i) { if (col[i] == 0) { for (j = 0; j < r; ++j) if (abs(r - j) == abs(row[j] - i)) break; if (j == r) { col[i] = 1; // 标记第i列，已存在Q row[j] = i; // 第j行的第i个元素放入Q dfs(r + 1, n, result); // 遍历第r + 1行 col[i] = 0; row[j] = 0; } } } } };
            
           
          
         
        
       
      
     
    
   

四. 小结

后续题目N-Queens II，其实比这一题简化许多，因为只要求输出解的个数，不需要输出所有解的具体状况。

?