八皇后 / N 皇后问题
哪些公司问过
文远知行1
答案要点
- 按行回溯,每行放一个皇后,行冲突天然避免
- 列、主对角线 row-col、副对角线 row+col 三组标记实现 O(1) 冲突判断
- 递归到第 n 行记录解,返回时撤销标记完成回溯
- 八皇后共 92 个解,时间上界 O(n!),空间 O(n)
- 可用位运算表示占用状态,用 x & -x 取最低可放位进一步加速
易错点
- 对角线下标写错,row-col 忘了加偏移导致负下标
- 递归返回后忘记撤销标记,导致后续分支判断错误
- 每次放置都遍历已放皇后检查冲突,复杂度多出一个 n 的因子
面试官常见追问
- 位运算版本怎么写?
- 如何输出所有棋盘而不是只计数?
- 如何利用对称性减少一半计算?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。