目录

一.题目介绍

二.问题分析

2-1整体思路

2-2算法分析

2-3举例

三.总代码

---

一.题目介绍

n皇后问题是指在国际象棋（8×8的棋盘）内放置8个皇后如何保证皇后之间不可互相攻击，找出所有可行的排放方式

皇后攻击范围是同一行、同一列、主对角线以及副对角线

二.问题分析

回溯算法是类似于暴力算法的一种，不过相较于暴力算法不对数据进行任何优化，回溯算法能在遍历的过程中不断进行剪枝，从而减少尝试次数，大部分回溯算法采用递归实现，本篇也是如此

2-1整体思路

（1）由题目可知每一行有且仅有一个皇后，故我们可以先固定行设为u，遍历当前u行的每一个位置寻找可摆放的位置即：已摆放的皇后的攻击范围之外

（2）对于如何记录已摆放的皇后的攻击范围可采用三个字符数组

    1.col[N]（记录当前位置列是否可被攻击）

    2.dg[N]（记录当前位置主对角线是否可被攻击）

    3.udg[N]（记录当前位置副对角线是否可被攻击）

（3）使用回溯算法（递归实现）探索所有可能

2-2算法分析

在分析算法前我们应先了解主对角线和副对角线对应坐标的表示方法

主对角线 dg ==列数 i +行数 u

副对角线 udg == 列数 i - 行数 u + 棋盘边长 n（防止相减为负数）  

void dfs(int u)
{
    if(u==n)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                cout << g[i][j];
            }
            cout << endl;
        }
        cout << endl;
        return;
    }
        
    for(int i=0;i<n;i++)
    {
    	if(!col[i]&&!dg[u+i]&&!udg[n-u+i])
    	{
    		g[u][i]='Q';
    		col[i]=dg[u+i]=udg[n-u+i]=true;
    		dfs(u+1);
    		col[i]=dg[u+i]=udg[n-u+i]=false;
    		g[u][i]='.';
		}
	}
}

1.进入dfs函数（参数是第u行），首先判断u是否==n（每行是否都已摆了一个皇后）若是则输出棋盘，后返回上一层递归

2.若u！=n，则进入for循环判断第u行第i列的位置是否在前u-1行已确定位置的Q的攻击范围之内

3.若不在则将（u，i）放置Q，且将其攻击范围存入col、dg、udg中

4.进入下一层递归即：u+1行寻找合适的位置

5.若在dfs（u+1）中所有行均以放置Q，或第u+1行所有位置均可被前u行攻击，则返回dfs（u）（第u行）将（u，i）上的Q取消、重置攻击范围

2-3举例

以n=4的棋盘为例

三.总代码

#include <iostream>
using namespace std;
const int N = 20;
//col是列,row是行 
int n;
char g[N][N]; //存储棋盘
bool col[N];
bool dg[N],udg[N];

void dfs(int u)
{
    if(u==n)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                cout << g[i][j];
            }
            cout << endl;
        }
        cout << endl;
        return;
    }
        
    for(int i=0;i<n;i++)
    {
    	//对角线性质:
		//主对角线==当前列数+当前行数
		//副对角线==当前列数-当前行数 
    	if(!col[i]&&!dg[u+i]&&!udg[n-u+i])
    	{
    		g[u][i]='Q';
    		col[i]=dg[u+i]=udg[n-u+i]=true;
    		//回溯触发条件:
			//1-1:dfs(u+1)到下一列时u!=n
			//1-2:当前行的每一列的元素都==false
			//导致dfs(u+1)未执行任何操作后返回到dfs(u)中执行回溯代码
			//2-1:此时u==n代码执行了输出操作后返回dfs(u)即上一次递归后执行回溯代码 
    		dfs(u+1);
    		col[i]=dg[u+i]=udg[n-u+i]=false;
    		g[u][i]='.';
		}
	}
}

int main()
{
    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            g[i][j] = '.';
        }
    dfs(0);
    
    return 0;
}