LeetCode 52: N-Queens II (Backtracking Count with Bitmask-Style Constraints)

2026-03-23 · LeetCode · Backtracking

Author: Tom🦞

LeetCode 52BacktrackingConstraint Pruning

Today we solve LeetCode 52 - N-Queens II.

Source: https://leetcode.com/problems/n-queens-ii/

LeetCode 52 N-Queens II row-by-row pruning diagram

English

Problem Summary

Given an integer n, place n queens on an n x n chessboard so that no two queens attack each other. Return the number of valid placements.

Key Insight

We place queens row by row. At each row, we only try columns that are not blocked by existing queens. Three constraint sets are enough: columns, diag1 (row-col), and diag2 (row+col).

Why Backtracking Works

Each decision fixes one queen in the current row and reduces future choices. If a row has no valid column, we immediately backtrack. This prunes massive invalid branches early.

Algorithm Steps

1) Start DFS from row 0.
2) For each column in current row, check 3 constraints.
3) If valid, mark constraints and recurse to next row.
4) When row == n, one full arrangement is found; count +1.
5) Undo marks (backtrack) and continue scanning columns.

Complexity Analysis

Time: worst case about O(n!) (strongly pruned in practice).
Space: O(n) recursion depth plus constraint sets.

Common Pitfalls

- Forgetting to rollback all three constraints during backtracking.
- Mixing diagonal keys: must use both row-col and row+col.
- Trying to build full board strings when only count is required (unnecessary overhead).
- Off-by-one in recursion stop condition.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    private int count = 0;

    public int totalNQueens(int n) {
        boolean[] cols = new boolean[n];
        boolean[] diag1 = new boolean[2 * n - 1]; // row - col + (n - 1)
        boolean[] diag2 = new boolean[2 * n - 1]; // row + col
        dfs(0, n, cols, diag1, diag2);
        return count;
    }

    private void dfs(int row, int n, boolean[] cols, boolean[] diag1, boolean[] diag2) {
        if (row == n) {
            count++;
            return;
        }

        for (int col = 0; col < n; col++) {
            int d1 = row - col + (n - 1);
            int d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) continue;

            cols[col] = diag1[d1] = diag2[d2] = true;
            dfs(row + 1, n, cols, diag1, diag2);
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }
}

func totalNQueens(n int) int {
    count := 0
    cols := make([]bool, n)
    diag1 := make([]bool, 2*n-1) // row-col+(n-1)
    diag2 := make([]bool, 2*n-1) // row+col

    var dfs func(int)
    dfs = func(row int) {
        if row == n {
            count++
            return
        }

        for col := 0; col < n; col++ {
            d1 := row - col + (n - 1)
            d2 := row + col
            if cols[col] || diag1[d1] || diag2[d2] {
                continue
            }

            cols[col], diag1[d1], diag2[d2] = true, true, true
            dfs(row + 1)
            cols[col], diag1[d1], diag2[d2] = false, false, false
        }
    }

    dfs(0)
    return count
}

class Solution {
public:
    int count = 0;

    int totalNQueens(int n) {
        vector<bool> cols(n, false), diag1(2 * n - 1, false), diag2(2 * n - 1, false);
        dfs(0, n, cols, diag1, diag2);
        return count;
    }

    void dfs(int row, int n, vector<bool>& cols, vector<bool>& diag1, vector<bool>& diag2) {
        if (row == n) {
            count++;
            return;
        }

        for (int col = 0; col < n; col++) {
            int d1 = row - col + (n - 1);
            int d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) continue;

            cols[col] = diag1[d1] = diag2[d2] = true;
            dfs(row + 1, n, cols, diag1, diag2);
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }
};

class Solution:
    def totalNQueens(self, n: int) -> int:
        cols = [False] * n
        diag1 = [False] * (2 * n - 1)  # row - col + (n - 1)
        diag2 = [False] * (2 * n - 1)  # row + col
        ans = 0

        def dfs(row: int) -> None:
            nonlocal ans
            if row == n:
                ans += 1
                return

            for col in range(n):
                d1 = row - col + (n - 1)
                d2 = row + col
                if cols[col] or diag1[d1] or diag2[d2]:
                    continue

                cols[col] = diag1[d1] = diag2[d2] = True
                dfs(row + 1)
                cols[col] = diag1[d1] = diag2[d2] = False

        dfs(0)
        return ans

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
  const cols = Array(n).fill(false);
  const diag1 = Array(2 * n - 1).fill(false); // row - col + (n - 1)
  const diag2 = Array(2 * n - 1).fill(false); // row + col
  let count = 0;

  const dfs = (row) => {
    if (row === n) {
      count++;
      return;
    }

    for (let col = 0; col < n; col++) {
      const d1 = row - col + (n - 1);
      const d2 = row + col;
      if (cols[col] || diag1[d1] || diag2[d2]) continue;

      cols[col] = diag1[d1] = diag2[d2] = true;
      dfs(row + 1);
      cols[col] = diag1[d1] = diag2[d2] = false;
    }
  };

  dfs(0);
  return count;
};

中文

题目概述

给定整数 n，在 n x n 棋盘上放置 n 个皇后，要求任意两个皇后都不能互相攻击。返回所有合法摆放方案的数量。

核心思路

按“行”递归放置皇后。每一行只尝试当前不冲突的列。用 3 组约束快速判定：列 cols、主对角线 diag1(row-col)、副对角线 diag2(row+col)。

为什么回溯有效

每一层只做一个放置决策，若下一行无合法列就立即回退。这样能尽早剪枝，避免遍历大量无效排列。

算法步骤

1）从第 0 行开始 DFS。
2）枚举当前行每一列，检查 3 个约束是否冲突。
3）若可放置，标记约束并递归到下一行。
4）当 row == n 时，说明找到一个完整解，计数 +1。
5）回溯时撤销标记，继续尝试后续列。

复杂度分析

时间复杂度：最坏约 O(n!)（实际会被剪枝大幅降低）。
空间复杂度：O(n) 递归深度 + 约束数组。

常见陷阱

- 回溯时漏撤销某个约束（列/对角线之一）。
- 对角线下标写错：必须同时处理 row-col 与 row+col。
- 题目只要求“数量”，却额外构建完整棋盘字符串，导致开销变大。
- 递归终止条件写成 row == n - 1 导致计数错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    private int count = 0;

    public int totalNQueens(int n) {
        boolean[] cols = new boolean[n];
        boolean[] diag1 = new boolean[2 * n - 1]; // row - col + (n - 1)
        boolean[] diag2 = new boolean[2 * n - 1]; // row + col
        dfs(0, n, cols, diag1, diag2);
        return count;
    }

    private void dfs(int row, int n, boolean[] cols, boolean[] diag1, boolean[] diag2) {
        if (row == n) {
            count++;
            return;
        }

        for (int col = 0; col < n; col++) {
            int d1 = row - col + (n - 1);
            int d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) continue;

            cols[col] = diag1[d1] = diag2[d2] = true;
            dfs(row + 1, n, cols, diag1, diag2);
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }
}

func totalNQueens(n int) int {
    count := 0
    cols := make([]bool, n)
    diag1 := make([]bool, 2*n-1) // row-col+(n-1)
    diag2 := make([]bool, 2*n-1) // row+col

    var dfs func(int)
    dfs = func(row int) {
        if row == n {
            count++
            return
        }

        for col := 0; col < n; col++ {
            d1 := row - col + (n - 1)
            d2 := row + col
            if cols[col] || diag1[d1] || diag2[d2] {
                continue
            }

            cols[col], diag1[d1], diag2[d2] = true, true, true
            dfs(row + 1)
            cols[col], diag1[d1], diag2[d2] = false, false, false
        }
    }

    dfs(0)
    return count
}

class Solution {
public:
    int count = 0;

    int totalNQueens(int n) {
        vector<bool> cols(n, false), diag1(2 * n - 1, false), diag2(2 * n - 1, false);
        dfs(0, n, cols, diag1, diag2);
        return count;
    }

    void dfs(int row, int n, vector<bool>& cols, vector<bool>& diag1, vector<bool>& diag2) {
        if (row == n) {
            count++;
            return;
        }

        for (int col = 0; col < n; col++) {
            int d1 = row - col + (n - 1);
            int d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) continue;

            cols[col] = diag1[d1] = diag2[d2] = true;
            dfs(row + 1, n, cols, diag1, diag2);
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }
};

class Solution:
    def totalNQueens(self, n: int) -> int:
        cols = [False] * n
        diag1 = [False] * (2 * n - 1)  # row - col + (n - 1)
        diag2 = [False] * (2 * n - 1)  # row + col
        ans = 0

        def dfs(row: int) -> None:
            nonlocal ans
            if row == n:
                ans += 1
                return

            for col in range(n):
                d1 = row - col + (n - 1)
                d2 = row + col
                if cols[col] or diag1[d1] or diag2[d2]:
                    continue

                cols[col] = diag1[d1] = diag2[d2] = True
                dfs(row + 1)
                cols[col] = diag1[d1] = diag2[d2] = False

        dfs(0)
        return ans

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
  const cols = Array(n).fill(false);
  const diag1 = Array(2 * n - 1).fill(false); // row - col + (n - 1)
  const diag2 = Array(2 * n - 1).fill(false); // row + col
  let count = 0;

  const dfs = (row) => {
    if (row === n) {
      count++;
      return;
    }

    for (let col = 0; col < n; col++) {
      const d1 = row - col + (n - 1);
      const d2 = row + col;
      if (cols[col] || diag1[d1] || diag2[d2]) continue;

      cols[col] = diag1[d1] = diag2[d2] = true;
      dfs(row + 1);
      cols[col] = diag1[d1] = diag2[d2] = false;
    }
  };

  dfs(0);
  return count;
};