回溯法求解八皇后问题

#include <iostream>
#include <vector>
#include <array>
#include <string>
using namespace std;

const int N = 8; //N皇后问题
//attack NxN的二维数组，true可放值皇后的位置，false不可放皇后的位置

//实现在(x,y)处放置皇后，并根据规则更新attack数组。
void put_queen(int x, int y, array<array<bool,N>,N> &attack)
{
    //180°、0°、90°、-90°、225°、135°、-45°、45°，皇后的8个攻击方向
    static const int dx[] ={-1,1,0,0, -1,-1,1,1};
    static const int dy[] ={0, 0,1,-1,-1,1,-1,1};
    int i,j,new_x,new_y;
    attack[x][y] = 1; //不能再放皇后的位置设为1
    for(i=0;i<8;i++) //8个方向
    {
        for(j=1;j<N;j++)
        {
            new_x = x + dx[i]*j;
            new_y = y + dy[i]*j;
            if(new_x >=0 && new_x < N && new_y >=0 && new_y < N)
            {
                attack[new_x][new_y] = false;//不能再放皇后的位置设为False
            }
            else break;//棋盘越界则停止该方向上的搜索
        }
    }
}


//回溯法求解N皇后问题的递归函数
void backtrack(int row, vector<string> &queen, array<array<bool,N>,N> attack, vector<vector<string>> &solve)
{
    //k 表示当前分析到的行号
    //queen 存储皇后的位置
    //attack 存储皇后的攻击范围
    //solve 存储N皇后问题的全部解法
    //退出递归的条件
    if(row==N) //找到一组解
    {
        solve.push_back(queen); //将结果queen存储到solve
        return;
    }
    //核心部分
    for(int col =0; col< N; col++)//遍历各列，回溯试探皇后可放的位置
    {
        if(attack[row][col])//如果k行i列可放（可放为true）
        {
            array<array<bool,N>,N> temp = attack;//备份attack数组，以待回溯
            queen[row][col] = 'Q';//放置皇后--标记为“Q"
            put_queen(row,col,attack);//更新attack数组
            backtrack(row+1,queen,attack,solve); //递归试探下一行
            attack = temp;//恢复attack数组
            queen[row][col]='.';//恢复queen数组
        }
    }
}


//设置棋盘初始状态，调用求解函数
vector<vector<string>> solveNQueens()
{
    vector<vector<string>> solve;
    array<array<bool,N>,N> attack;
    vector<string> queen;
    //设置初始状态
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            attack[i][j] = true;//初始全部位置可放皇后(可放则为true)
        }
        queen.push_back("");
        queen[i].append(N,'.');//初始全部位置都无皇后，以点号表示
    }
    backtrack(0,queen,attack,solve);//调用backtrack函数求解
    return solve;
}


int main()
{
    vector<vector<string>> solve = solveNQueens();
    cout <<"棋盘大小为"<<N <<"x"<<N<< "时，N皇后问题总共有"<< solve.size() <<"组解："<<endl;
    //cout <<sizeof(bool)<<endl;
    for(int i=0; i< solve.size(); i++)
    {
        cout <<"第"<< i+1 <<"组解："<<endl;
        for(int row=0;row<N; row++)
        {
            cout<<solve[i][row]<<endl;
        }
        cout<<endl;
    }
    return 0;
}