N皇后问题经典DFS

作者：Li_阴宅 | 2024-07-14 16:01:25

踩

N皇后问题经典DFS

题目 HDU 2553“N皇后问题”

通过这个题学习到了剪枝。暴力破解会超时啊，就很拿人。DFS的难点在于扩展子节点的时候如何构造停止递归并返回的条件，就要用到剪枝函数。

依然举个例子，分析一下4皇后怎么搞。

从第一行开始放皇后：第一行从左到右有4种方案，产生4个结点；第2行，排除同列和斜线，拓展新的结点，注意不用排除同行，因为第二行和第一行已经是不同行的了。继续拓展第三行和第四行，结束。

这下应该很明白了吧！

这个题其实用BFS和DFS都可以写，但是DFS毕竟比BFS代码量更少。

设左上角是原点

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/825414