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

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more