大家好，我来给你们讲讲怎么用深度优先搜索来解决N皇后问题。就是在n乘n的棋盘上放n个皇后，让它们谁也不攻击谁。N皇后问题要求给每一行放一个皇后，而且它们不能在同一行、同一列，也不能在对角线上。我们的目标是找出所有可能的摆放方案，然后用字符串数组的形式把它们表示出来，其中'Q'代表皇后，'.'代表空位。比如说当n是4的时候，有两种方案，另一种是每个方案都有两种不同的排列方式。还有一种情况就是当n等于1时，只有一种可能的方案。这里面涉及到一个问题重述：把皇后放在棋盘上，让它们互相不攻击。要在n乘n的棋盘上依次放置n个皇后，并且任意两个皇后不同行、不同列、也不在对角线上。任务是输出所有合法摆放方案。 现在我们来说说深度优先搜索：规则一次判断要把棋盘抽象成四个布尔数组：行、列、对角线和反对角线状态记录。每次搜索的时候会用四个参数递归：当前行号x，当前列号y，已放皇后数s还有棋盘大小n。每一步只有两种选择：要么不放皇后直接跳到下一列继续搜索；要么放皇后检查是否安全再继续递归下一行。 时间复杂度分析的话是O(n!)，因为每一行只能放一个皇后，而且必须按顺序依次摆放。第一行有n种选择方法，第二行有n-1种方法，依次类推直到第n行只有1种方法。所以总的时间复杂度还是n!。 现在来说说代码骨架：只需四步就能跑起来。先定义一个Solution类，里面包含棋盘大小、列、对角线还有反对角线状态记录这几个变量。还有所有解集和当前路径这两个vector变量。接着就是solveNQueens函数用来初始化变量并调用dfs函数开始搜索。dfs函数内部就是递归过程了：如果已经到了棋盘的边界就把当前路径加入解集并返回；否则继续尝试往下搜索或者向右移动一列再试一次。这里有个小技巧就是对角线和反对角线的索引需要做一些偏移处理以避免越界问题。最后返回解集就大功告成了！