51. N皇后

• 题号：51
• 来源：LeetCode
• 难度：困难
• 标签：回溯 递归
• 语言：TypeScript
• 解法：1 个
• 作者：lmliheng
• 最近更新：2026-09-27

TypeScript · O(n!) 时间 · O(n) 空间 · 更新于 2026-09-27

逐行回溯，列与两条对角线剪枝

/**
 * @difficulty hard
 * @tags 回溯,递归
 * @time O(n!)
 * @space O(n)
 * @note 逐行回溯，列与两条对角线剪枝
 * @51. N 皇后
 */
function solveNQueens(n: number): string[][] {
    const ans: string[][] = [];
    const queens = Array(n).fill(0); // 皇后放在 (r,queens[r])
    const col = Array(n).fill(false);
    const diag1 = Array(n * 2 - 1).fill(false);
    const diag2 = Array(n * 2 - 1).fill(false);
    function dfs(r: number) {

        if (r === n) {
            console.log(queens)
            ans.push(queens.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - 1 - c)));
            return;
        }
        // 在 (r,c) 放皇后
        for (let c = 0; c < n; c++) {
            const rc = r - c + n - 1;
            if (!col[c] && !diag1[r + c] && !diag2[rc]) { // 判断能否放皇后
                queens[r] = c; // 直接覆盖，无需恢复现场
                col[c] = diag1[r + c] = diag2[rc] = true; // 皇后占用了 c 列和两条斜线
                dfs(r + 1);
                col[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场
            }
        }
    }
    dfs(0);
    return ans
};

源码：ts/leetcode/51. N皇后.ts

---

在 GitHub 上查看题目所在目录：lmliheng/algorithm