C++八皇后问题

缺乏、安全感 2022-12-28 09:17 86阅读 0赞

八皇后问题是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。

问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

像这样的棋盘：

![Queen][]

对棋盘行和列标号，可以使用 `0~7` 或 `1~8`，通过行数与列数进行加减计算，得到如下的内容：

![Queen\_leftLine.png][Queen_leftLine.png]

![Queen\_rightLine.png][Queen_rightLine.png]

`行 - 列` 和 `行 +列`，可以清晰的看到具有很明显的规律

`行 - 列` ，红线的方向，从左到右，从上到下的斜线，取值范围 `[-7 ， 7]`,，共15个元素

-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7

`行 +列`，红线的方向，从左到右，从下到上的斜线，取值范围 `[2 ， 16]` 或 `[0 ， 14]` ，共15个元素

当列和行标号范围 "1~8"
    2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
    
    当列和行标号范围 "0~7"
    0,1,2,3,4,5,6,7,8,9,10,11,12,13,14

解题方法 ：

注 ：**此处使用行列的标号范围 "1~8"**

设置数组，判断某位置是否处于一个安全的位置

**1. 建立数组，并初始化**

因为每种斜线最多有15种可能，行列最多只有8种可能
    
    // 判断左斜线
    int r[16] 	= { 0 };
    // 判断左斜线
    int l[16] 	= { 0 };
    // 判断列
    int h[8] = { 0 };

例如： 取 x = 4， y = 5 位置，其左斜线 -1 ，右斜线 9 ，列 4

由于数组初始化为0，当填入一行皇后，需要进行占位，利用行列号来修改数组位置的值，修改为1

左斜线(x-y)取值范围：[-7 , 7] ，因此在左斜线 x-y+8, 则对应数组 l[1] 到 l[15] 
    
    右斜线(x+y)取值范围：[2 , 16] ，因此在右斜线 x+y-1则对应数组 r[1] 到 r[15]

例如：取 x = 4， y = 5 位置，`4-5=-1`,`4+5=9` ,因此 `l[7]=1`、`r[8]=1`

**2. 创建数组保存每种情况 , 并统计数量**

// 符合条件的数量
    int n = 0;
    int que[8]	= { 0 };

创建一维数组，来存放每行皇后的位置，每个皇后的取值都不同，也就是取值由0到7

**3. 创建函数，输出保存数组的情况**

void Print()
    // 输出
    {
    	cout << "第"<<n << "种：" ;
    	for (int i = 0; i < 8; ++i)
    	{
    		cout << que[i] ;
    	}
    	cout << endl;
    }

**4. 设计递归函数**

递归参数为行数

void Queen(int row = 0)
    // 输入行数
    {
          // 函数出口
    	if(row > 7)
    	{
    		n++;
    		Print();
    		return;
    	}
    	for (int i = 0; i < 8; ++i)
    	{
    		// 当一行到结尾，也没有找到解法，结束，返回上一行，
    		if(i>7)
    		{
    			return;
    		}
            // 判断是否符合条件
    		if( !l[row-i+8] && !r[row+i-1] && !h[i])
    		{
                // 符合条件保存该行的位置，并标记影响的斜线和列 
    			que[row] = i;
    
    			h[i] = 1;
    			l[row-i+8] = 1;
    			r[row+i-1]= 1;
                
                // 本行已找到，跳到下一行
    			Queen(row+1);
    
    			// 因为下一行没有找到位置，结束函数，此行该位置不能得到的结果，因此清除之前设置的内容
    			que[row] = 0;
    
    			l[row-i+8] = 0;
    			r[row+i-1]= 0;
    			h[i] = 0;
    		}
    	}
    }

例子：

#include<iostream>
    #include<string>
    #include<stdlib.h>
    using namespace std;
    
    
    // 符合条件的数量
    int n = 0;
    // 数组存放每行皇后的位置
    int que[8]  = { 0 };
    
    // 判断左斜线
    int l[16] 	= { 0 };
    // 判断左斜线
    int r[16] 	= { 0 };
    // 判断列
    int h[8] = { 0 };
    
    void Print()
    // 输出
    {
    	cout << "第"<<n << "种：" ;
    	for (int i = 0; i < 8; ++i)
    	{
    		cout << que[i] ;
    	}
    	cout << endl;
    }
    
    void Queen(int row = 0)
    // 输入行数
    {
          // 每次递归结束的出口
    	if(row > 7)
    	{
            // 完成一次递归，结果加一，并打印，结束递归
    		n++;
    		Print();
    		return;
    	}
    	for (int i = 0; i < 8; ++i)
    	{
    		// 当一行到结尾，也没有找到解法，结束，返回上一行，
    		if(i>7)
    		{
    			return;
    		}
            // 判断是否符合条件
    		if( !l[row-i+8] && !r[row+i-1] && !h[i])
    		{
                // 符合条件保存该行的位置，并标记影响的斜线和列 
    			que[row] = i;
    
    			h[i] = 1;
    			l[row-i+8] = 1;
    			r[row+i-1]= 1;
                
                // 本行已找到，跳到下一行
    			Queen(row+1);
    
    			// 因为下一行没有找到位置，结束函数，此行该位置不能得到的结果，因此清除之前设置的内容
    			que[row] = 0;
    
    			l[row-i+8] = 0;
    			r[row+i-1]= 0;
    			h[i] = 0;
    		}
    	}
    }
    int main(int argv,char* argc[])
    {
    	Queen();
    	cout << n <<endl;
    	system("pause");
    	return 0;
    }

## N皇后问题 ##

通过八皇后可以推出N皇后的问题的解决方案

主要问题在于斜线的区间和数量

**注：行列的标号范围 "1~n"**

当为N皇后，x+y的取值范围 `[2 , 2n]` , x-y 取值范围 `[ 1-n , n-1 ]` , 数量都为 `2n-1`

#include<iostream>
    #include<cstdlib>
    
    using namespace std;
    
    template<int size>
    class Queen
    {
    private:
    	int num = 0;
    	// 判断左斜线
    	int l[size*2] = { 0 };
    	// 判断左斜线
    	int r[size*2] = { 0 };
    	// 判断列
    	int h[size] = { 0 };
    	// 数组
    	int que[size] = { 0 };
    public:
    	Queen(){};
    	~Queen(){};
    public:
    	void check(int row = 0)
    	{
    		if(row >= size)
    		{
    			num++;
    			Prints();
    			return;
    		}
    		for (int i = 0; i < size; ++i)
    		{
    			if( !l[row-i+size] && !r[row+i-1] && !h[i])
    			{
    				que[row] = i;
    				h[i] = 1;
    				l[row-i+size] = 1;
    				r[row+i-1]= 1;
    				
    				check(row+1);
    				// 因为下一行没有找到，因此此行该位置不能得到应有的结果，因此清空设置的内容
    
    				que[row] = 0;
    				l[row-i+size] = 0;
    				r[row+i-1]= 0;
    				h[i] = 0;
    			}
    		}
    	}
    	void Prints()
    	// 输出
    	{
    		cout << "第"<<num << "种：" ;
    		for (int i = 0; i < 8; ++i)
    		{
    			cout << que[i] ;
    		}
    		cout << endl;
    	}
    };
    
    int main(int argc, char const *argv[])
    {
    	Queen<8> Sir;
    	Sir.check();
    	system("pause");
    	return 0;
    }

[Queen]: /images/20221120/84eed3557d1e492c839332fe518b6af0.png
[Queen_leftLine.png]: /images/20221120/624af9eb37a14812b3eb8ac962aa9ef1.png
[Queen_rightLine.png]: https://img-blog.csdnimg.cn/img_convert/5f6b6129f06cddc699102676127f3cf9.png