Skip to main content

Leetcode 51: N-Queens


1. Problem Statement (Simple Explanation):


You must place n queens on an n x n chessboard such that:

  • No two queens attack each other:

    • Not in the same row

    • Not in the same column

    • Not on the same diagonal

You must return all distinct solutions. Each solution is an n-element array of strings, where:

  • 'Q' is a queen

  • '.' is an empty cell

Each string represents one row of the board.


2. Examples:


Example 1:


Input:

n = 4

Output:

[

  [".Q..","...Q","Q...","..Q."],

  ["..Q.","Q...","...Q",".Q.."]

]

These represent the two valid 4-queens solutions.


Example 2:


Input:

n = 1

Output:

[["Q"]]

One queen on a 1x1 board.


3. Approach – Backtracking with Column & Diagonal Constraints:


We place queens row by row:

  • For each row r, we choose a column c where:

    • No queen in the same column.

    • No queen in the same diagonal.

We track which columns and diagonals are already under attack to ensure O(1) checks.


Representing Constraints:


For an n x n board:

  • Columns: index c in [0, n-1]

    • colUsed[c] = true if some queen is already in column c.

  • Main diagonals (top-left to bottom-right):

    • All squares with same r - c are on the same main diagonal.

    • To avoid negative indices, map:

      • diag1Index = r - c + (n - 1)

    • So diag1Used size is 2n - 1.

  • Anti-diagonals (top-right to bottom-left):

    • All squares with same r + c are on the same anti-diagonal.

    • diag2Index = r + c, also in [0, 2n-2].

    • Use diag2Used of size 2n - 1.


Backtracking State:


  • board: an n x n char grid or list of strings (we’ll build rows via positions).

  • row: current row index to place a queen.

  • Arrays:

    • colUsed[n]

    • diag1Used[2n-1]

    • diag2Used[2n-1]

  • positions[row] = column where we placed the queen in that row (helps build final string board).


Algorithm (Step-by-Step):


  1. Initialize tracking arrays to false.

  2. Use a recursive function backtrack(row):

    • If row == n:

      • We have a complete placement.

      • Build the board representation from positions and add to result.

      • Return.

    • Else:

      • For each column c from 0 to n-1:

        • Compute d1 = row - c + (n - 1), d2 = row + c.

        • If colUsed[c] or diag1Used[d1] or diag2Used[d2] is true: skip.

        • Otherwise:

          • Place queen: set

            • positions[row] = c

            • colUsed[c] = diag1Used[d1] = diag2Used[d2] = true

          • Recurse backtrack(row + 1).

          • Backtrack: unset the above.

  3. Start with backtrack(0).

  4. Return all collected boards.


Pseudo-code:



Complexity:


  • N-Queens has no simple closed-form complexity; it’s exponential/backtracking:

    • Worst-case time grows roughly faster than polynomial; but:

      • n <= 9 here, and the number of solutions is manageable.

  • Space:

    • O(n) for recursion depth and arrays (excluding output).


4. Java code:



5. C code:


C implementation is similar to C++ logic, but you need:

  • Arrays bool colUsed[9], bool diag1Used[17], bool diag2Used[17].

  • int positions[9].

  • Backtracking that fills results as char*** etc.

Given the complexity of pointer bookkeeping, most people prefer Java/C++/Python/JS for this problem.



6. C++ code:



7. Python code:



8. JavaScript code:



Comments

Post a Comment