【数据结构】N皇后（递归经典算法）-蒲公英云

【数据结构】N皇后（递归经典算法）

一、N皇后

1、题目
将n个皇后摆放在N*N的棋盘中，互相不可攻击，有多少种摆放方式，每种摆放方式具体是怎样的？

2、解题思路
解题思路：
1、将棋盘放在一个二维数组中，同时设置方向数组：
static const int dx[] = {-1,1,0,0,-1,-1,1,1,};
static const int dy[] = {-1,0,-1,1,-1,1,-1,1};
分别按照方向数组的8个方向分别延伸N个问题，只要不超过边界，mark[][] = 1;其余为0；
2、对于N*N的棋盘，每行都要放置1个且只能放置1个皇后，利用递归对棋盘的每一行放置皇后，放置时，按列顺序寻找可以放置皇后的列，若可以放置皇后，将皇后放置该位置，并更新mark标记数组，递归进行下一行皇后放置，当该次递归结束后，恢复mark数组，并尝试下一个可能放皇后的列；当递归可以完成N列的N个皇后放置，则将该结果保存并返回。
3、棋盘的设置与皇后的放置

4、N皇后回溯算法
70 1
5、程序实现

#include<iostream>
#include<vector>
using namespace std;
void put_down_the_queue(int x, int y, 
                        std::vector<std::vector<int>>& mark)
{
    static const int dx[] = {-1,1,0,0,-1,-1,1,1};
    static const int dy[]= {0,0,-1,1,-1,1,-1,1};
    mark[x][y] = 1;
    for(int i = 1;i< mark.size();i++)
    {
        for(int j = 0; j < 8; j++)
        {
            int new_x = x + i*dx[j];//*********************
            int new_y = y + i*dy[j];//**********************
            if( (new_x>=0 && new_x<mark.size()) && (new_y >=0&&new_y<mark.size()) )//注意>=********************
            {
                mark[new_x][new_y] = 1;
            }
        }
    }
}
class solution
{
public:
    std::vector<std::vector<std::string>> solveNQuess(int n)
    {
        std::vector<std::vector<std::string>> result;
        std::vector<std::vector<int>> mark;
        std::vector<std::string> location;
        for(int i = 0;i<n;i++)
        {
            mark.push_back(std::vector<int>());
            for(int j = 0; j <n;j++)
            {
                mark[i].push_back(0);
            }
            location.push_back("");
            location[i].append(n,'.');
        }
        generate(0,n,location,result,mark);
        return result;
    }
private:
    void generate(int k, int n,
                   std::vector<std::string>&location,
                   std::vector<std::vector<std::string>>&result,
                   std::vector<std::vector<int>> &mark
                   )
    {
        if(k == n)
        {
            result.push_back(location);
            return ;
        }
        for(int i = 0; i<n; i++)
        {
            if(mark[k][i] == 0)
            {
                std::vector<std::vector<int>> tmp_mark = mark;
                location[k][i] = 'Q';
                put_down_the_queue(k,i,mark);
                generate(k+1, n, location,result,mark);
                mark = tmp_mark;
                location[k][i] = '.';
            }
        }
    }
};
int main()
{
    std::vector<std::vector<std::string>> result;
    solution solve;
    result = solve.solveNQuess (4);
    for(int i = 0; i<result.size();i++)
    {
        printf("i = %d\n",i);
        for(int j = 0; j<result[i].size();j++)
        {
            printf("%s\n",result[i][j].c_str() );
        }
        printf("\n");
    }
    return 0;
}