八皇后问题_C/C++/C#

八皇后问题

问题描述：

八皇后问题
八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。

本题是数据结构回溯算法的实际应用。

#include
#include
using namespace std;
class Queen
{
public:
    Queen(int n);
    ~Queen();
    void SetQueen();        //填写n皇后（即开始放置皇后）
    void PrintQueen();       //打印皇后位置

private:
    int Place(int k);    //判断皇后k是否冲突
    int* x;              //皇后的位置
    int num;             //皇后的个数
};
Queen::Queen(int n)
{
    x = new int[n];             //可以近似理解为二维数组，x表示行下标，n表示列下标
    memset(x, -1, n);          //将新开辟的数组都置为-1，表示未摆放皇后
    num = n;
}
Queen::~Queen()
{
    delete[]x;
}
void Queen::SetQueen()
{
    int k = 0, count = 0;       //count存储解的个数
    while (k >= 0)           //摆放皇后k,注意0<=k=4):";
    cin >> n;              //输入皇后个数
    Queen Q{n};            //创建对象Q
    Q.SetQueen();         //调用对象Q的函数摆放皇后
    return 0;
}

注意：在八皇后问题中的n输入最小应该4，如果小于4假定n为3的话通过画图可以得出第三个皇后没有下脚的地方。故n应该大于等于4

例如n=4时，运行结果：

本题参考《数据结构–从概念到C++实现（第3版）》。

初次驾到，如有错误，还请斧正。

八皇后问题

C/C++/C#相关栏目本月热门文章