Leetcode – 52. N-Queens II

🏰 Solving the N-Queens Problem with Backtracking

The N-Queens problem is a classic in algorithms and interview prep. It asks:

Place N queens on an NĂ—N chessboard so that no two queens attack each other.

Queens can attack vertically, hori…


This content originally appeared on DEV Community and was authored by Rakesh Reddy Peddamallu

🏰 Solving the N-Queens Problem with Backtracking

The N-Queens problem is a classic in algorithms and interview prep. It asks:

Place N queens on an NĂ—N chessboard so that no two queens attack each other.

Queens can attack vertically, horizontally, and diagonally. The task is to count the total number of valid arrangements.

✨ Key Insight

When placing queens row by row:

  • Each row can have only one queen.
  • Each column can have only one queen.
  • Each diagonal can have only one queen.

So, at each step, we just need to check if placing a queen in the current cell (r, c) is safe. If yes → place it and recurse to the next row.

⚙️ Backtracking Approach

We use recursion to try all possible placements:

  1. Row by row recursion – Start from row 0, and for each column, check if placing a queen is valid.
  2. Use sets for quick lookup:
  • col: columns where queens are already placed.
  • posDiag: positive diagonals (r + c is constant).

  • negDiag: negative diagonals (r - c is constant).

    1. If a position (r, c) is safe:

  • Place queen → add to sets.

  • Recurse for next row.

  • Backtrack → remove from sets.

    1. When r === n, we found a valid arrangement → increment result.

🖥️ Implementation (JavaScript) 

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function (n) {
    let col = new Set();
    let posDiag = new Set();
    let negDiag = new Set();
    let res = 0;

    const backtrack = (r) => {
        if (r === n) {
            res += 1;  // Found a valid board
            return;
        }

        for (let c = 0; c < n; c++) {
            // Check if queen can be placed
            if (col.has(c) || posDiag.has(r + c) || negDiag.has(r - c)) {
                continue;
            }

            // Place queen
            col.add(c);
            posDiag.add(r + c);
            negDiag.add(r - c);

            // Recurse to next row
            backtrack(r + 1);

            // Backtrack (remove queen)
            col.delete(c);
            posDiag.delete(r + c);
            negDiag.delete(r - c);
        }
    };

    backtrack(0);
    return res;
};

⏱️ Time & Space Complexity

  • Time Complexity: O(N!)

    • In the worst case, we try N options for row 1, N-1 for row 2, and so on.
    • The actual branching is smaller due to pruning (invalid placements), but O(N!) is a safe upper bound.

  • Space Complexity: O(N)

    • Sets col, posDiag, and negDiag hold at most N elements.
    • Recursion stack depth is N.

âś… Example Run

For n = 4, the valid solutions are 2:

. Q . .      . . Q .
. . . Q      Q . . .
Q . . .      . . . Q
. . Q .      . Q . .

The function correctly returns 2.

🎯 Final Thoughts

  • This problem is a perfect introduction to backtracking because you learn how to try, prune, and backtrack.
  • Sets make the lookup O(1), which is much cleaner than scanning the board every time.
  • Once you master this, you can extend it to actually return the board configurations instead of just counting them.


This content originally appeared on DEV Community and was authored by Rakesh Reddy Peddamallu


Print Share Comment Cite Upload Translate Updates
APA

Rakesh Reddy Peddamallu | Sciencx (2025-08-30T13:00:15+00:00) Leetcode – 52. N-Queens II. Retrieved from https://www.scien.cx/2025/08/30/leetcode-52-n-queens-ii/

MLA
" » Leetcode – 52. N-Queens II." Rakesh Reddy Peddamallu | Sciencx - Saturday August 30, 2025, https://www.scien.cx/2025/08/30/leetcode-52-n-queens-ii/
HARVARD
Rakesh Reddy Peddamallu | Sciencx Saturday August 30, 2025 » Leetcode – 52. N-Queens II., viewed ,<https://www.scien.cx/2025/08/30/leetcode-52-n-queens-ii/>
VANCOUVER
Rakesh Reddy Peddamallu | Sciencx - » Leetcode – 52. N-Queens II. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2025/08/30/leetcode-52-n-queens-ii/
CHICAGO
" » Leetcode – 52. N-Queens II." Rakesh Reddy Peddamallu | Sciencx - Accessed . https://www.scien.cx/2025/08/30/leetcode-52-n-queens-ii/
IEEE
" » Leetcode – 52. N-Queens II." Rakesh Reddy Peddamallu | Sciencx [Online]. Available: https://www.scien.cx/2025/08/30/leetcode-52-n-queens-ii/. [Accessed: ]
rf:citation
» Leetcode – 52. N-Queens II | Rakesh Reddy Peddamallu | Sciencx | https://www.scien.cx/2025/08/30/leetcode-52-n-queens-ii/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts