蓝桥杯--N皇后问题

Dear 丶 2021-09-29 20:06 405阅读 0赞

在了解N皇后问题之前我们先看一下，一个古老而著名的问题：

### 八皇后问题 ###

该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击 **(同一行、同一列、同一斜线上的皇后都会自动攻击)，** 问有多少种摆法?

### N皇后问题 ###

N皇后问题是八皇后问题的推广，即在一个NxN的棋盘上放置N个皇后，使其不能互相攻击 **(同一行、同一列、同一斜线上的皇后都会自动攻击)** 那么问，有多少种摆法？

不管是N皇后还是八皇后甚至于之后的2N皇后都是很经典的递归、回溯问题

今天打算从新回顾一下皇后问题，所以在此留下笔记，本人愚钝，若行文有误望谅解。

具体思路：

首先确定放的方式，我在这里放的方式就是我们惯性思维的放置，先放第一行，再放第二行，再放第二行.....

然后就是细化每一步放置的操作，每一步放置的操作其实有2个：

1、判断这一行中有没有符合放置条件的位置（在不在同一行、在不在同一列、在不在对角线）所以在这里我就必须得到所有已经放置的皇后的位置（也就是第二步中记录下来的位置数组）

2、进行放置，放置的操作我们可以理解为两个步骤，第一个是记录下当前位置（这里我用了两个数组存放已经放置的皇后的行和列），第二就是进行下一个皇后的放置（这里就可以进入下一个递归）

最后就是递归的结束条件，因为我是按照每一行放的，所以一共有N个皇后，我成功放完第N行之后就表示这种方法是符合题意的，ans就会记录，然后回溯到上一步操作，继续去模拟下一个情况。

代码如下：

#include<iostream>
    #include<cString>
    #include<string.h>
    #include<cmath>
    #include<algorithm> 
    #define MAPSIZE 100
    using namespace std;
    int N;//皇后的个数
    int ans = 0;//计数
    int R[MAPSIZE]={0},C[MAPSIZE] = {0};//存放已经放置的皇后的行和列的 
    void NQuee(int row)//递归函数
    {
    	if(row>N)//所有皇后都已经放完 
    	{
    		ans++;//方法加一 
    		return;
    	}
    	for(int i=1;i<=N;i++)//模拟当前行的皇后的放入
    	{
    		bool tag = true;//标识符，表示当前位置是否满足放入的条件 
    		for(int j=1;j<row;j++)
    		{
    			if(!(row!=R[j]&&i!=C[j]&&(abs(row-R[j])!=abs(i-C[j]))))//不满足条件
    			{
    				tag = false;//设置标志 
    				break; 
    			}	
    		}
    		if(tag)//满足放入的条件
    		{
    			R[row] = row;C[row] = i;//记录当前的皇后存放的行和列
    			NQuee(row+1);
    			R[row] = 0;C[row] = 0;//当这种情况判断完之后撤销皇后的放入
    		}
    	}
    }
    int main() 
    {
    	cin>>N;//输入皇后的个数
    	NQuee(1);
    	cout<<ans<<endl;
    	return 0;
    }