DFS算法 ---- N皇后问题

上一篇讲完了DFS与BFS的基础知识，这期给大家带来用DFS解决问题的例子。

有一个N * N的棋盘，每行每列每斜线仅限有一个皇后，请问共有多少种放置皇后的方法？

咱们这道题涉及到图的遍历问题，肯定会优先想到DFS算法，咱们这道题同样以走迷宫的DFS为分析基础，?首先想DFS内部的形参应该取什么含义？

这道题的限制条件为每行每列每斜线都仅有一个皇后，所以形参含义为第几行，通过对列的遍历直到找到全部方案。

咱们先看一个伪代码：

void DFS(int x)
{
    if(x == n)
    {
        res++;
        return ;
    }
    for(int i = 0;i < n;i++)
    {
        if(Check(i,x))
        {
            (记录);//刷新
            DFS(x + 1);
        }
    }
}

接下来咱们就只需要分析其限制条件与如何记录不会重复搜索就可以了。

分析限制条件，在这道题要求咱们每行每列每斜线仅有一个皇后，所以这里咱们定义一个col数组表示col[x] = i，其含义为第x行的第i列放置皇后，随后，其限制条件就可以：

bool Check(int i,int x)
{
    for(int j = 0;j < x;j++)  //行的遍历
    {
        if(col[j] == i || (abs(col[j] - i) == abs(j - x)))  //abs函数取绝对值
            return false;
    }
    return true;
}

最后结合两段代码：

int res = 0;  //计数
?int col[];  //存放行的哪一列上放有皇后
bool Check(int i,int x)
{
    for(int j = 0;j < x;j++)  //行的遍历
    {
        if(col[j] == i || (abs(col[j] - i) == abs(j - x)))  //abs函数取绝对值
            return false;
    }
    return true;
}
void DFS(int x)
{
    if(x == n)  //递归结束，所有行已放完皇后
    {
        res++;  //计数
        return ;
    }
    for(int i = 0;i < n;i++)
    {
        if(Check(i,x))  //判断
        {
            col[x] = i;  //第x行的第i列存放皇后
            DFS(x + 1);
        }
    }
}
int main()
{
    ....;
}
?

好了，今天就到这里了，记得三连支持，感谢收看。?