C++八皇后问题_牛客博客

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

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

像这样的棋盘：

Queen

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

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

行 - 列 ，红线的方向，从左到右，从上到下的斜线，取值范围 [-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;
}