2021-02-16:n皇后问题。给定一个整数n，返回n皇后的摆法有多少种？

Question

2021-02-16:n皇后问题。给定一个整数n，返回n皇后的摆法有多少种？

Answer 1

递归的思想与运用

#include <iostream>
#include <list>

using namespace std;

template <int SIZE>
class QueueSolution
{
protected:
    enum { N = SIZE + 2}; // 包含边界元素

    struct Pos
    {
        Pos(int px = 0, int py = 0) : x(px), y(py)
        {}
        int x;
        int y;
    };

    int m_chessboard[N][N];  // 棋盘
    Pos m_direction[3];      // 3方向数组 （左下、正下、右下）
    list<Pos> m_solution;    // 放置皇后位置的解决方案
    int m_count;             // 解的数量

    void init()
    {
        m_count = 0;

        // 边界填充
        for (int i=0; i<N; i+=(N-1))
        {
            for (int j=0; j<N; ++j)
            {
                m_chessboard[i][j] = 2;
                m_chessboard[j][i] = 2;
            }
        }

        // 棋位填充
        for (int i=1; i<=SIZE; ++i)
        {
            for (int j=1; j<=SIZE; ++j)
            {
                m_chessboard[i][j] = 0;
            }
        }

        // 方向数组填充
        m_direction[0].x = -1;  // ↙
        m_direction[0].y = -1;
        m_direction[1].x = 0;   // ↓
        m_direction[1].y = -1;
        m_direction[2].x = 1;   // ↘
        m_direction[2].y = -1;
    }

    void print()
    {
        // 当前解的八皇坐标
        for (auto iter = m_solution.cbegin(); iter != m_solution.cend(); ++iter)
        {
            cout << "(" << iter->x << "," << iter->y << ")" << " ";
        }

        cout << endl;

        for (int i=0; i<N; ++i)
        {
            for (int j=0; j<N; ++j)
            {
                switch (m_chessboard[i][j])
                {
                    case 0 : cout << "."; break;
                    case 1 : cout << "#"; break;
                    case 2 : cout << "*"; break;
                }
                //cout << hex << m_chessboard[i][j];
            }
            cout << endl;
        }

        cout << endl;
    }

    bool check(int x, int y, int d)
    {
        bool flag = true;

        do
        {
            x += m_direction[d].x;
            y += m_direction[d].y;
            flag = flag && (m_chessboard[x][y] == 0);

        }while (flag); // 当棋位不为空（到达边界或有棋子）退出

        return (m_chessboard[x][y] == 2); // 检查是否到达棋盘边界
    }

    // 核心算法 ！！
    void run(int j)
    {
        if (j <= SIZE)  // 1. 位置查找
        {
            for (int i=1; i<=SIZE; ++i)               // 1.1 尝试 j 行的每一列
            {
                if (check(i, j, 0) && check(i, j, 1) && check(i, j, 2))  // 1.1。1 检查棋位是否可用
                {
                    m_chessboard[i][j] = 1;           // 1.1.2 棋位标记
                    m_solution.push_back(Pos(i, j));
                    run(j + 1);                       // 1.1.3 查找 j +1 行
                    
                    // 1.1.4 擦除棋位标记
                    // 当查找成功时，run 会不断递归查找 j + 1 行，直到 j == SIZE 时，打印结果；
                    // 当运行到这里，说明 j + 1 行位置查找失败或j == SIZE一次查找成功，即 j 行的位置是错误的，擦除标记，继续尝试 j 行的下一列元素（for(...)）
                    m_chessboard[i][j] = 0;           
       
                    m_solution.pop_back();
                }
            }
        }
        else  // 2. 递归出口，[1-SIZE] 找到解决方案
        {
            m_count ++;
            print();
        }
    }

public:
    QueueSolution()
    {
        init();
    }

    void run()
    {
        run(1);

        cout << "Total : " << m_count << endl;
    }
};

int main()
{
    QueueSolution<8> qs;

    qs.run();

    return 0;
}