回溯法求解N皇后问题是否可能达到O(n²)时间复杂度？

回溯法求解N皇后问题的最坏时间复杂度公认结论为O(n!)，你在两份技术资料里看到的O(n²)标注属于典型的内容笔误，不存在支撑该结论的合理逻辑，具体原因如下：

• 你对代码逻辑的判断完全准确：标准逐行放置的回溯实现，第一行共有n个可选列位置，放置完第一个皇后之后，第二行受同列、两条对角线的攻击规则约束，最多剩余n-1个合法位置，第三行最多剩余n-2个合法位置，以此类推，总枚举量级为n*(n-1)*(n-2)*…*1 = n!。哪怕实现中做了剪枝提前跳过冲突位置，最坏场景下的时间复杂度上界依然是O(n!)，这是国内外算法教材、权威技术资料统一的结论，不存在学术争议。
• 资料中标注的O(n²)是典型的张冠李戴错误：O(n²)是N皇后问题单解构造法的时间复杂度，这类解法完全不做回溯枚举，而是利用N皇后解的数学规律，按固定规则逐行直接放置皇后，不需要试探和回退，整个填充过程仅需遍历n行，每行做线性级的规则计算，总复杂度为O(n²)。资料撰写者把构造法的复杂度错套到了回溯实现上，才会出现和贴出的代码逻辑完全矛盾的复杂度标注。
• 这类公开技术教程站点的内容多为众包贡献，审核疏漏非常常见：同站点的其他N皇后相关教程条目里，也存在正确标注回溯法O(n!)复杂度的内容，属于版本迭代、内容更新时的笔误，不是复杂度研究出现了新的颠覆性结论。

补充判断技巧：算法复杂度结论必须和实现逻辑严格对应。只要代码存在递归回溯、逐层枚举可选位置、冲突后回退的逻辑，就不可能出现多项式级的O(n²)复杂度——N皇后是经典的NP难问题，回溯作为带剪枝的暴力搜索类解法，复杂度必然是阶乘量级。

内容的提问来源于stack exchange，提问作者JobHunter69