排列与 N 皇后思想
放置元素并在冲突时回溯
排列与 N 皇后思想 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
从子集到排列
一个permutation是按某种顺序排列所有元素的结果。生成它们是继子集之后要掌握的下一项回溯技能。🔀
有多少个排列
n 个元素共有 n 的阶乘个排列，因为第一个位置有 n 种选择，下一个位置有 n 减一种选择，以此类推。数量增长得非常快。
一次放置一个元素
递归会从左到右填充各个位置。每一步选择一个未使用的元素，将其放入当前位置，然后对剩余元素进行递归。
跟踪已使用的元素
布尔已使用数组会标记哪些元素已经放置，因此每个元素在每个排列中都会恰好出现一次。
代码中的排列
这个回溯过程会放置一个未使用的值，进行递归，然后将它释放，以供下一个分支使用。
def perm(cur):
if len(cur) == n:
out.append(cur[:]); return
for x in a:
if x not in cur:
perm(cur + [x])允许时使用迭代工具库
在快速竞赛中，Python 的 itertools.permutations会提供所有排列，无需您自行编写递归。
from itertools import permutations
for p in permutations(a):
print(p)N 皇后问题
N 皇后问题要求您在 n×n 的棋盘上放置 n 个皇后，使它们互不攻击。这是经典的回溯难题。👑
每行放置一个皇后
由于任意两个皇后都不能处于同一行，您可以每行放置一个皇后，只需选择它所在的列。这样会大幅缩小搜索范围。
检查三类冲突
放置前，请拒绝任何已被占用的列或对角线。使用集合记录已占用的列和两个方向的对角线。
if c in cols or r-c in d1 or r+c in d2:
continue在走入死路时回溯
如果某一行没有可用的列，该分支就失败。请回溯，移除最后一个皇后，然后尝试它的下一个选项。
共同模式
排列和 N 皇后问题有着相同的结构：选择、递归、撤销。一旦看清这一点，大多数放置类难题都可以套用同一个模板。
快速检查
为什么 N 皇后问题每行只放置一个皇后？
回顾：选择、递归、撤销
您通过放置未使用的元素生成了permutations，并学到了 N 皇后问题使用相同的选择、递归、撤销模式，同时检查冲突。🎯
常见问题解答
「排列与 N 皇后思想」课时是免费的吗？
是的 — 「排列与 N 皇后思想」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「排列与 N 皇后思想」这节课中我会学到什么？
放置元素并在冲突时回溯 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「排列与 N 皇后思想」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 递归思考：基础情况与递归
- 生成所有子集
- 排列与 N 皇后思想
- 剪枝以应对时间限制