LintCode: N皇后问题I and II

主要是借鉴网上一篇博客的思路链接
1、N皇后问题(http://www.lintcode.com/zh-cn/problem/n-queens/)

n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击。

给定一个整数n，返回所有不同的n皇后问题的解决方案。

每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。

您在真实的面试中是否遇到过这个题？ Yes
样例
对于4皇后问题存在两种解决的方案：

[

[".Q..", // Solution 1

 "...Q",

 "Q...",

 "..Q."],

["..Q.", // Solution 2

 "Q...",

 "...Q",

 ".Q.."]

]

挑战
你能否不使用递归完成？

标签
递归 深度优先搜索
相关题目

class Solution {
public:
/**
 * Get all distinct N-Queen solutions
 * @param n: The number of queens
 * @return: All distinct solutions
 * For example, A string '...Q' shows a queen on forth position
 */
vector<vector<string> > solveNQueens(int n) {  
// write your code here 
vector<vector<string>> res;
if(n<=0)  
return res;  
vector<int> c(n);

vector<string> level(n,"");
for(int i=0;i<n;++i){
for(int j=0;j<n;++j)
                level[i].push_back('.');
        }
        search(c,n,0,res,level);  
return res;  
    }  

void search(vector<int> &c,int n,int cur,vector<vector<string>> &res,vector<string> &level){ 
if(cur==n){  
            res.push_back(level);
return;
        }

for(int i=0;i<n;++i){  //cur表示当前行,i表要选择的列 
if(isValid(c,cur,i)){       //检验当前列是否合法 
                c[cur]=i;//合法的话就摆放吧
string s(n,'.');
                level[cur].replace(0,n,s);
                level[cur].replace(i,1,"Q");
                search(c,n,cur+1,res,level);  //搜寻下一行 
            }
        }      
    }

bool isValid(vector<int> &c,int row,int col){  
for(int i=0;i<row;++i)  
if(c[i]==col||i-c[i]==row-col||i+c[i]==row+col) //分别检查纵向,主对角线,副对角线上是否有其他皇后 
return false;//因为是一行一行摆放,所以不用检查同一行
return true;          
    }  
};

2、 N皇后问题II
根据n皇后问题，现在返回n皇后不同的解决方案的数量而不是具体的放置布局。(http://www.lintcode.com/zh-cn/problem/n-queens-ii/)

class Solution {
public:
/**
 * Get all distinct N-Queen solutions
 * @param n: The number of queens
 * @return: All distinct solutions
 * For example, A string '...Q' shows a queen on forth position
 */
vector<vector<string> > solveNQueens(int n) {  
// write your code here 
vector<vector<string>> res;
if(n<=0)  
return res;  
vector<int> c(n);

vector<string> level(n,"");
for(int i=0;i<n;++i){
for(int j=0;j<n;++j)
                level[i].push_back('.');
        }
        search(c,n,0,res,level);  
return res;  
    }  

void search(vector<int> &c,int n,int cur,vector<vector<string>> &res,vector<string> &level){ 
if(cur==n){  
            res.push_back(level);
return;
        }

for(int i=0;i<n;++i){          
if(isValid(c,cur,i)){
                c[cur]=i;
string s(n,'.');
                level[cur].replace(0,n,s);
                level[cur].replace(i,1,"Q");
                search(c,n,cur+1,res,level); 
            }
        }      
    }

bool isValid(vector<int> &c,int row,int col){  
for(int i=0;i<row;++i)  
if(c[i]==col||i-c[i]==row-col||i+c[i]==row+col) 
return false;
return true;          
    }  
};