【数据结构】N皇后（递归经典算法）

爱被打了一巴掌 2022-05-16 13:07 213阅读 0赞

## 一、N皇后 ##

**1、题目**  
将n个皇后摆放在N\*N的棋盘中，互相不可攻击，有多少种摆放方式，每种摆放方式具体是怎样的？

**2、解题思路**  
解题思路：  
1、将棋盘放在一个二维数组中，同时设置方向数组：  
static const int dx\[\] = \{-1,1,0,0,-1,-1,1,1,\};  
static const int dy\[\] = \{-1,0,-1,1,-1,1,-1,1\};  
分别按照方向数组的8个方向分别延伸N个问题，只要不超过边界，mark\[\]\[\] = 1;其余为0；  
2、对于N\*N的棋盘，每行都要放置1个且只能放置1个皇后，利用递归对棋盘的每一行放置皇后，放置时，按列顺序寻找可以放置皇后的列，若可以放置皇后，将皇后放置该位置，并更新mark标记数组，递归进行下一行皇后放置，当该次递归结束后，恢复mark数组，并尝试下一个可能放皇后的列；当递归可以完成N列的N个皇后放置，则将该结果保存并返回。  
**3、棋盘的设置与皇后的放置**  
![70][]

**4、N皇后回溯算法**  
![70 1][]  
**5、程序实现**

#include<iostream>
    #include<vector>
    using namespace std;
    
    void put_down_the_queue(int x, int y, 
    						std::vector<std::vector<int>>& mark)
    {
    	static const int dx[] = {-1,1,0,0,-1,-1,1,1};
    	static const int dy[]= {0,0,-1,1,-1,1,-1,1};
    
    	mark[x][y] = 1;
    
    	for(int i = 1;i< mark.size();i++)
    	{
    		for(int j = 0; j < 8; j++)
    		{
    			int new_x = x + i*dx[j];//*********************
    			int new_y = y + i*dy[j];//**********************
    			if( (new_x>=0 && new_x<mark.size()) && (new_y >=0&&new_y<mark.size()) )//注意>=********************
    			{
    				mark[new_x][new_y] = 1;
    			}
    		}
    	}
    }
    class solution
    {
    public:
    	std::vector<std::vector<std::string>> solveNQuess(int n)
    	{
    		std::vector<std::vector<std::string>> result;
    		std::vector<std::vector<int>> mark;
    		std::vector<std::string> location;
    		for(int i = 0;i<n;i++)
    		{
    			mark.push_back(std::vector<int>());
    			for(int j = 0; j <n;j++)
    			{
    				mark[i].push_back(0);
    			}
    			location.push_back("");
    			location[i].append(n,'.');
    		}
    		generate(0,n,location,result,mark);
    		return result;
    	}
    
    private:
    	void generate(int k, int n,
    		           std::vector<std::string>&location,
    				   std::vector<std::vector<std::string>>&result,
    				   std::vector<std::vector<int>> &mark
    				   )
    		          
    	{
    		if(k == n)
    		{
    			result.push_back(location);
    			return ;
    		}
    
    		for(int i = 0; i<n; i++)
    		{
    			if(mark[k][i] == 0)
    			{
    				std::vector<std::vector<int>> tmp_mark = mark;
    				location[k][i] = 'Q';
    				put_down_the_queue(k,i,mark);
    
    				generate(k+1, n, location,result,mark);
    				mark = tmp_mark;
    				location[k][i] = '.';
    			}
    		}
    	}
    
    };
    
    int main()
    {
    	std::vector<std::vector<std::string>> result;
    	solution solve;
    	result = solve.solveNQuess (4);
    
    	for(int i = 0; i<result.size();i++)
    	{
    		printf("i = %d\n",i);
    		for(int j = 0; j<result[i].size();j++)
    		{
    			printf("%s\n",result[i][j].c_str() );
    		}
    		printf("\n");
    	}
    	return 0;
    }

**6、结果展示**  
![70 2][]

[70]: /images/20220516/d9c1f675a56b414b8e960721d653a569.png
[70 1]: /images/20220516/a05d75d394194522a568f11b59082d93.png
[70 2]: /images/20220516/35ec00086fd64979ad3ffbfad680a5be.png